bzoj1051Tarjan裸题

时间：2023-12-03 11:11:14

tarjan缩点+判断出度为0的点

所以不需要新建边

 #include <cstdio>

 int n,m,p,q,N=,time=,T=,sum=,ans=;

 int from[],to[],nex[],fir[],dfn[],low[],l[],tar[],gui[],c[];

 bool que[];

 void add(int p,int q){    from[++N]=p,to[N]=q,nex[N]=fir[p],fir[p]=N;}

 int min(int p,int q){    return (p<q)?p:q;}

 void dfs(int k)

 {

     dfn[k]=low[k]=++time,l[++T]=k,que[k]=;

     for(int o=fir[k];o;o=nex[o])

         if(!dfn[to[o]])

             dfs(to[o]),low[k]=min(low[k],low[to[o]]);

         else

             if(que[to[o]])

                 low[k]=min(low[k],dfn[to[o]]);

     if(dfn[k]==low[k])

     {

         sum++;

         while(l[T]!=k)

             que[l[T]]=,tar[l[T--]]=sum,gui[sum]++;

         que[k]=;tar[k]=sum;T--;gui[sum]++;

     }

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;i++)

         scanf("%d%d",&p,&q),add(p,q);

     for(int i=;i<=n;i++)

         if(!dfn[i]) dfs(i);

     for(int i=;i<=N;i++)

     if(tar[from[i]]!=tar[to[i]])

         c[tar[from[i]]]=;

     for(int i=;i<=sum;i++)

         if(!c[i])

             if(ans){    printf("0\n");return ;}

             else ans=gui[i];

     printf("%d\n",ans);

     return ;

 }

tarjan差点写错，心碎

相关文章