社区讨论

萌新刚学OI,代码40求调

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

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@lo37amwj
此快照首次捕获于
2023/10/24 01:57
2 年前
此快照最后确认于
2023/10/24 01:57
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
#define N 100001
using namespace std;
queue <int> q;
vector <int> V1[N];
vector <int> V2[N];
int to[N],nex[N],beg[N];
int dis[N];
int ans[N],tot,x,y,v,d[N],u,n,m,sum,vis[N];
int dfn[N],low[N],f[N],times,e;
int stack_[N],w[N],visit[N],cnt,cnt2,cnt3;
inline void add(int x,int y) {
	to[++e]=y;
	nex[e]=beg[x];
	beg[x]=e;
}
void tarjan(int x) {
	dfn[x]=low[x]=++times;
	stack_[++cnt3]=x;
	visit[x]=1;
	for(int i=beg[x]; i; i=nex[i]) {
		if(!dfn[to[i]]) {
			tarjan(to[i]);
			low[x]=min(low[x],low[to[i]]);
		} 
		else if(visit[to[i]])
			low[x]=min(low[x],dfn[to[i]]);
	}
	int y;
	if(low[x]==dfn[x]) {
		cnt2++;
		do{
			y=stack_[cnt3];
			cnt3--;
			visit[y]=0;
			vis[y]=cnt2;
			dis[cnt2]++;
		}while(x!=y);
	}
}
int main() {
	memset(beg,-1,sizeof(beg));
	int n,m,x,y;
	cin>>n>>m;
	for(int i=1; i<=m; i++) {
		cin>>x>>y;
		add(x,y);
	}
	for(int i=1; i<=n; i++)
		if(!dfn[i])tarjan(i);
	for(int i=1; i<=n; i++) {
		for(int j=beg[i];j;j=nex[j]){
			int y=to[j];
			if(vis[i]!=vis[y]){
				d[vis[i]]++;
			}
		}
	}
	x=0;
	for(int i=1; i<=cnt2; i++) {
		if(!d[i]){
			if(x){
				cout<<0;
				return 0;
			}
			x=i;
		}
	}
	cout<<dis[x];
	return 0;
}

回复

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

正在加载回复...