1 条题解
-
0Tethys LV 9 @ 2020-09-13 10:50:11
#include<bits/stdc++.h>
#define next netusing namespace std;
int size[1000005],ans,u[1000005],d[1000005],sum,a,b,n,m,tp,head[1000005],dfn[1000005],cnt,num,low[1000005],st[10000005];
bool vis[1000005];inline int read(){
char ch=getchar();
int op=1,opp=0;
while(ch>'9'||ch<'0'){
if(ch=='-') op=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
opp=opp*10+(ch-'0');
ch=getchar();
}
return op*opp;
}struct node{
int u,v,next;
}edge[5000005];inline void add_edge(int x,int y){
edge[++cnt].u=x;
edge[cnt].v=y;
edge[cnt].next=head[x];
head[x]=cnt;
}inline void tarjan(int x){
low[x]=dfn[x]=++num;
st[++tp]=x;
vis[x]=1;
for(int i=head[x];i!=0;i=edge[i].next){
if(!dfn[edge[i].v]){
tarjan(edge[i].v);
low[x]=min(low[x],low[edge[i].v]);
}else{
if(vis[edge[i].v]){
low[x]=min(low[x],dfn[edge[i].v]);
}
}
}
if(dfn[x]==low[x]){
int y;
sum++;
do{
y=st[tp--];
vis[y]=0;
d[y]=sum;
size[sum]++;
}while(x!=y);
}
}int main(){
n=read();m=read();
for(int i=1;i<=m;i++){
a=read();
b=read();
add_edge(a,b);
}
for(int i=1;i<=n;i++){
if(dfn[i]==0) tarjan(i);
}
for(int i=1;i<=n;i++){
for(int j=head[i];j!=0;j=edge[j].next){
if(d[i]==d[edge[j].v]) continue ;
else u[d[i]]=1;
}
}
for(int i=1;i<=sum;i++){
if(u[i]==0){
if(ans!=0){
ans=0;
break;
}
ans=size[i];
}
}
cout<<ans<<endl;
return 0;
}
- 1
信息
- 难度
- 5
- 分类
- (无)
- 标签
- 递交数
- 95
- 已通过
- 33
- 通过率
- 35%
- 上传者