tarjan 全wa求调
查看原帖
tarjan 全wa求调
749665
huta0楼主2024/1/20 10:01
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define a_all a.begin(),a.end()
using namespace std;
typedef long long ll;
int n,m;
int dfn[10010],low[10010];
int siz[10010],cnt,tot,top;
int stk[10010],instk[10010];
bool vis[10010];
struct edge {
	int v;
};
vector<edge> e[10010];
vector<vector<int>> ans;
void tarjan(int x) {
	dfn[x]=low[x]=++tot;
	stk[++top]=x,instk[x]=1;
	vis[x]=1;
	for(edge ed:e[x]) {
		if(!dfn[ed.v]) {
			tarjan(ed.v);
			low[x]=min(low[x],low[ed.v]);
		} else if(instk[ed.v])
		    low[x]=min(low[x],dfn[ed.v]);
	}
	if(dfn[x]==low[x]) {
		int y; ++cnt;
		vector<int> v;
		do {
			y=stk[top--];
			instk[y]=0;
			v.push_back(y);
			//cout<<y<<" ";
			siz[cnt]++;
		} while(y!=x);
		//cout<<endl;
		sort(v.begin(),v.end());
		ans.push_back(v);
	}
}
int main() {
	cin.tie(0); cout.tie(0);
	cin>>n>>m;
	memset(stk,0,sizeof(stk));
	memset(instk,0,sizeof(instk));
	memset(siz,0,sizeof(siz));
	memset(vis,0,sizeof(vis));
	rep(i,1,m) {
		int a,b;
		cin>>a>>b;
		e[a].push_back({b});
	} 
	rep(i,1,n) {
		if(!vis[i]) tarjan(i);
	}
	cout<<ans.size()<<endl;
	for(int i=ans.size()-1;i>=0;i--) {
		for(int k : ans[i])
		   cout<<k<<" ";
		cout<<endl;   
	}
    return 0;
}
2024/1/20 10:01
加载中...