結果

問題 No.1254 補強への架け橋
ユーザー furafura
提出日時 2020-10-09 21:56:03
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 157 ms / 2,000 ms
コード長 1,938 bytes
コンパイル時間 2,553 ms
コンパイル使用メモリ 209,212 KB
最終ジャッジ日時 2025-01-15 04:35:08
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 123
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:78:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   78 |         int n; scanf("%d",&n);
      |                ~~~~~^~~~~~~~~
main.cpp:82:31: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   82 |                 int u,v; scanf("%d%d",&u,&v); u--; v--;
      |                          ~~~~~^~~~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

using graph=vector<vector<int>>;

void add_undirected_edge(graph& G,int u,int v){
	G[u].emplace_back(v);
	G[v].emplace_back(u);
}

class two_edge_connected_components{
	int idx;
	vector<int> ord,low,id;
	const graph& G;

	vector<vector<int>> Comp;
	vector<pair<int,int>> B;
	graph Tr;

	void dfs1(int u,int p){
		ord[u]=low[u]=idx++;
		bool f=true;
		for(int v:G[u]){
			if(v==p && f){ f=false; continue; }
			if(ord[v]==-1){
				dfs1(v,u);
				low[u]=min(low[u],low[v]);
			}
			else{
				low[u]=min(low[u],ord[v]);
			}
		}
	}

	void dfs2(int u,int p){
		if(p==-1 || ord[p]<low[u]){
			id[u]=idx++;
			if(p!=-1) B.emplace_back(minmax(p,u));
		}
		else{
			id[u]=id[p];
		}
		for(int v:G[u]) if(id[v]==-1) dfs2(v,u);
	}

public:
	two_edge_connected_components(const graph& G):G(G){
		int n=G.size();

		idx=0;
		ord.assign(n,-1);
		low.assign(n,-1);
		rep(u,n) if(ord[u]==-1) dfs1(u,-1);

		idx=0;
		id.assign(n,-1);
		rep(u,n) if(id[u]==-1) dfs2(u,-1);

		Comp.resize(idx);
		Tr.resize(idx);
		rep(u,n){
			Comp[id[u]].emplace_back(u);
			for(int v:G[u]) if(id[u]!=id[v]) Tr[id[u]].emplace_back(id[v]);
		}
	}

	int operator[](int i)const{ return id[i]; }

	const vector<int>& component(int i)const{ return Comp[i]; }
	const vector<pair<int,int>>& bridges()const{ return B; }
	const graph& bridge_block_tree()const{ return Tr; }
};

int main(){
	int n; scanf("%d",&n);
	graph G(n);
	vector<pair<int,int>> E(n);
	rep(i,n){
		int u,v; scanf("%d%d",&u,&v); u--; v--;
		add_undirected_edge(G,u,v);
		E[i]={u,v};
	}

	two_edge_connected_components TECC(G);
	vector<int> id(n);
	rep(i,TECC.bridge_block_tree().size()) for(int u:TECC.component(i)) id[u]=i;

	vector<int> ans;
	rep(i,n) if(id[E[i].first]==id[E[i].second]) ans.emplace_back(i);
	printf("%ld\n",ans.size());
	rep(i,ans.size()) printf("%d%c",ans[i]+1,i+1<ans.size()?' ':'\n');

	return 0;
}
0