社区讨论

求助,56分tarjan缩点

P2341[USACO03FALL / HAOI2006] 受欢迎的牛 G参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lytho7ey
此快照首次捕获于
2024/07/20 10:07
2 年前
此快照最后确认于
2024/07/20 10:54
2 年前
查看原帖
邻接数组存图,tarjan缩点,统计出度。
#4 WA
#2,#9,#10,#11,#12,#13,#14,#18,#19,#20 RE
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> g[200000];
int c[200000],cl,dfn[200000],low[200000],dfnd,sf[200000],jl[200000],jd,f[200000],sz[200000];
//  环编号 ,top,dfs序  ,返祖边,   dfs深度,入栈, dfs路径,前者top,出度,环大小 
void tarjan(int x){
	dfn[x]=++dfnd;
	low[x]=dfn[x];
	sf[x]=1;
	jl[++jd]=x;
	for(int i=0;i<g[x].size();i++){
		if(!dfn[g[x][i]]){
			tarjan(g[x][i]);
			low[x]=min(low[x],low[g[x][i]]);
		}else if(sf[i]){
			low[x]=min(low[x],dfn[g[x][i]]);
		}
	}
	if(dfn[x]==low[x]){
		cl++;
		while(jl[jd]!=x){
			c[jl[jd]]=cl;
			sf[jl[jd]]=0;
			sz[cl]++;
			jd--;
		}
		c[jl[jd]]=cl;
		sz[cl]++;
		sf[jl[jd]]=0;
		jd--;
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			dfnd=0;
			tarjan(i);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<g[i].size();j++){
			if(c[i]!=c[g[i][j]]){
				f[c[i]]++;
			}
		}
	}
	int sff=0,jll;
	for(int i=1;i<=cl;i++){
		if(!f[i]){
			sff++;
			jll=i;
		}
	}
	if(sff>1){
		cout<<0;
		return 0;
	}else{
		cout<<sz[jll];
	}
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...