仅AC on #6求调
查看原帖
仅AC on #6求调
247917
dongzimo楼主2024/10/25 16:56
#include<bits/stdc++.h>
using namespace std;
int n,m,u,v,cnt,sc;
vector<int> g[10005];
stack<int> s;
priority_queue<int,vector<int>,greater<int> >scc[10005];//记录强连通分量中包含的节点 
int dfn[10005],low[10005],idx;
bool vis[10005];
int sccc[10005];//记录节点所在的强连通分量 
void tarjan(int x){
	dfn[x]=low[x]=++cnt;
	vis[x]=1;
	s.push(x);
	for(int i=0;i<g[x].size();i++){
		int idx=g[x][i];
		if(!dfn[idx]){
			tarjan(idx);
			low[x]=min(low[x],low[idx]);
		}
		else if(vis[idx])
			low[x]=min(low[x],dfn[idx]);
	}
	if(low[x]==dfn[x]){
		sc++;
		scc[sc].push(x);
		sccc[x]=sc;
		while(s.top()!=x){
			scc[sc].push(s.top());
			s.pop();
			sccc[s.top()]=sc;
			vis[s.top()]=0;
		}
		s.pop();
		vis[x]=0;
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		g[u].push_back(v);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			tarjan(i);
	cout<<sc<<endl;
	bool flag;
	for(int i=1;i<=n;i++){
		idx=sccc[i];
		if(!scc[idx].empty()){
			while(!scc[idx].empty()){
				cout<<scc[idx].top()<<' ';
				scc[idx].pop();
				if(scc[idx].empty())
				cout<<endl;
			}
		}
	}
	return 0;
} 
2024/10/25 16:56
加载中...