tarjan求调
查看原帖
tarjan求调
437243
cly312楼主2024/8/16 15:11
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int> e[N];
int dfn[N],low[N],cnt;
vector<pair<int,int>> ans;
void tarjan(int u,int fa){
	dfn[u]=low[u]=++cnt;
	for(auto v:e[u]){
		if(!dfn[v]){
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>dfn[u]){
				ans.push_back(make_pair(min(u,v),max(u,v)));
			}
		}
		else if(dfn[v]<dfn[u]&&v!=fa) low[u]=min(low[u],dfn[v]);
	}
	return;
}


int main(){
	int n;
	while(cin>>n){ 
		cnt=0;
		memset(dfn,0,sizeof(dfn));
		memset(low,0,sizeof(low));
		ans.clear();
		for(int i=1;i<=n;i++){
			int u,v,T;
			char _;
			cin>>u>>_>>T>>_;
			u++; 
			while(T--){
				cin>>v;
				v++;
				e[u].push_back(v); 
			} 
		}
		for(int i=1;i<=n;i++){
			if(!dfn[i]) tarjan(i,0);
		}
		sort(ans.begin(),ans.end());
		cout<<ans.size()<<" critical links"<<endl;
		for(int i=0;i<ans.size();i++) cout<<ans[i].first-1<<" - "<<ans[i].second-1<<endl;
		cout<<endl;
	}
	
	return 0;
} 
2024/8/16 15:11
加载中...