蒟蒻求助,新学tarjan
查看原帖
蒟蒻求助,新学tarjan
250036
Authentic_k楼主2021/1/28 08:07

求助大佬12分

#include<bits/stdc++.h>
using namespace std;
const int N=10000,M=1000010;
int ver[M],nxt[M],head[N],dfn[N],low[N],ans1[M],edge[M],j[M],cu[M],d[M];
int stuck[N],ins[N],c[N],ans,ji;
vector<int> scc[N];
int n,m,num,tot,cnt,top;
int hc[M],vc[M],nc[M],tc;
void add(int x,int y){
	ver[++tot]=y;
	nxt[tot]=head[x];
	head[x]=tot;
}
void add_c(int x,int y){
	 vc[++tc]=y;
	 nc[tc]=hc[x];
	 hc[x]=tc;
	
}
void tarjan(int x){
	dfn[x]=++num;
	low[x]=num;
	stuck[++top]=x,ins[x]=1;
	for(int i=head[x];i;i=nxt[i]){
		if(!dfn[ver[i]]){
			low[x]=min(low[x],low[ver[i]]);}
			else if(ins[ver[i]]){
				low[x]=min(low[x],dfn[ver[i]]);
			}
		
		
	}
	if(dfn[x]==low[x]){
		cnt++;
		int y;
		do{
			y=stuck[top--];
			ins[y]=0;
			c[y]=cnt,scc[cnt].push_back(y); 
			j[cnt]++;
		}while(x!=y);
	}
	
}
int main(){
	cin>>n>>m;
//	for(int i=1;i<=n;i++){
//		int h;
//		cin>>h;
//		edge[i]=h;
//	}
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		add(x,y);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(i);
	}

//	for(int i=1;i<=cnt;i++){
//		for(int k=1;k<=j[i];k++){
//			cout<<scc[i][k]<<endl;
//			ans1[i]+=edge[scc[i][k]];
//		}
//	}
int k=1;
    for(int i=1;i<=999;i++){
    	d[i]=1;
    }
	for(int i=2;i<=tot;i++){
		
		if(c[i]==c[i-1]) 
		{
		d[k]++;
		continue;
		}
		else{
			add_c(c[i],c[i-1]);
			k++;
			cu[k-1]++;
		}
	}
	for(int i=1;i<=k;i++){
		if(cu[i]==0) ji++;
		
	}
//	cout<<cu[5]<<endl<<cu[3]<<endl;
//	cout<<ji;
	if(ji!=1) cout<<0;
	else{
		for(int i=1;i<=k;i++){
		if(cu[i]==0) cout<<d[i];
		
	}
	}
}

2021/1/28 08:07
加载中...