tarjan对了一个点求助
查看原帖
tarjan对了一个点求助
809371
Love_Natsu楼主2024/3/9 09:19

对了#6

#include <bits/stdc++.h>
#define N 10005
using namespace std;
int n,m,low[N],dfn[N],d_ord,in_sta[N],u,v,zu,vis[N],b[N];
vector<int> e[N],ans[N];
stack<int> s;
bool cmp(vector<int> x,vector<int> y){
	if(x.size()==0)return 0;
	if(y.size()==0)return 1;
	return x[0]<=y[0];
}
void Tarjan(int u){
	dfn[u]=low[u]=++d_ord;
	s.push(u);in_sta[u]=1;
	for(int v:e[u]){
		if(!dfn[v]){
			Tarjan(v);
			low[u]=min(low[v],low[u]);
		}
		else if(in_sta[v])low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
	    zu++;
	    ans[zu].push_back(u);
	    while(s.top()!=u){
	    	b[s.top()]=zu;
	    	ans[zu].push_back(s.top());
	    	s.pop();
	    	in_sta[s.top()]=0;
		}
		s.pop();
		in_sta[u]=0;
		b[u]=zu;
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	while(m--){
		cin>>u>>v;
		e[u].push_back(v);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])Tarjan(i);
	for(int i=1;i<=zu;i++)sort(ans[i].begin(),ans[i].end());
	cout<<zu<<"\n";
	for(int i=1;i<=n;i++){
		if(vis[b[i]])continue;
		vis[b[i]]=1;
		for(int j=0;j<ans[b[i]].size();j++)cout<<ans[b[i]][j]<<" ";
		cout<<"\n";
	}
	return 0;
}
2024/3/9 09:19
加载中...