社区讨论
萌新刚学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 条回复,欢迎继续交流。
正在加载回复...