結果

問題 No.1254 補強への架け橋
ユーザー 👑 Nachia
提出日時 2020-10-09 21:48:10
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 161 ms / 2,000 ms
コード長 1,227 bytes
コンパイル時間 1,863 ms
コンパイル使用メモリ 172,768 KB
実行使用メモリ 26,728 KB
最終ジャッジ日時 2024-07-20 10:31:37
合計ジャッジ時間 14,425 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 123
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

const int xN = 100000;

int N, M;
vector<int> E[xN], rE[xN];
int I[xN], rI[xN];
int P[xN], H[xN];
LL ans = 0;

int DFS1(int p, int i = 0) {
	for (int e : E[p]) {
		if (P[p] == e) continue;
		rE[e].push_back(p);
		if (P[e] != -1) continue;
		P[e] = p;
		i = DFS1(e, i);
	}
	I[p] = i; rI[i] = p; ++i;
	return i;
}
void DFS2(int p, int s) {
	if (rI[I[p]] != p) return;
	H[p] = s;
	for (int e : rE[p]) {
		if (I[e] > I[s]) continue;
		if (H[e] != -1) continue;
		DFS2(e, s);
	}
}
void strongDc() {
	rep(i, N) P[i] = I[i] = H[i] = -1;
	rep(i, N) {
		if (P[i] != -1) continue;
		P[i] = i;
		int Z = DFS1(i);
		for (int i = Z - 1; i != -1; i--) if (H[rI[i]] == -1) DFS2(rI[i], rI[i]);
	}
}

vector<pair<int, int>> J;

int main() {
	cin >> N;
	rep(i, N) {
		int u, v; cin >> u >> v; u--; v--;
		J.push_back({ u,v });
		E[u].push_back(v);
		E[v].push_back(u);
	}

	strongDc();

	vector<int> ans;

	rep(i, N) {
		if (H[J[i].first] == H[J[i].second]) ans.push_back(i);
	}

	cout << ans.size() << endl;
	rep(i, ans.size()) { if (i) cout << " "; cout << (ans[i] + 1); } cout << endl;

	return 0;
}
0