【玄关 tarjan】全WA求助
查看原帖
【玄关 tarjan】全WA求助
659165
mysterys楼主2023/11/27 18:52

rtrt

#include<bits/stdc++.h>//tarjan
using namespace std;
int n,m,Times,scc;
vector<int>v[10005];
stack<int>sta;
int dfn[10005],low[10005];
vector<int>rd[10005];//记录强联通分量
bool vis[10005];
void tarjan(int x){
	dfn[x]=low[x]=++Times;
	vis[x]=true;
	sta.push(x);
	for(int i=0;i<v[x].size();i++){
		int kkk=v[x][i];
		if(dfn[kkk]==0){
			tarjan(kkk);
			low[x]=min(low[x],low[kkk]);
		}
		else if(vis[kkk]){
			low[x]=min(low[x],low[kkk]);
		}
	}
	if(dfn[x]==low[x]){
		scc++;
		bool flag=true;
		while(flag){
			int t=sta.top();
			sta.pop();
			vis[t]=false;
			rd[scc].push_back(t);
			if(t==x)
				flag=false;
		}
	}
}
bool cmp(int a,int b){
	return a>b;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,d;
		cin>>u>>d;
		v[u].push_back(d);
	}
	tarjan(1);
	cout<<scc<<'\n';
	memset(vis,false,sizeof(vis));
	for(int i=n;i>=1;i--){
		bool flag=0;
		if(!vis[i]){
			stable_sort(rd[i].begin(),rd[i].end(),cmp);
			for(int j=rd[i].size()-1;j>=0;j--){
				cout<<rd[i][j]<<' ';
				flag=1;
			}
		}
		if(flag){
			cout<<'\n';
			vis[i]=1;
		}
	}
	return 0;
}
2023/11/27 18:52
加载中...