1 条题解

  • 0
    @ 2020-09-13 10:50:11

    #include<bits/stdc++.h>
    #define next net

    using 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%
上传者