bzoj1051（明星奶牛）

这道就是明星奶牛，A了一次又一次了，(⊙o⊙)…(⊙o⊙)…

去年pas就打了不下5次，就是强联通缩点，然后求出度为0的块

判断有多个的话就无解，一个就输出块的大小。

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include<cstring>

 using namespace std;

 const int NN=1e4+,MM=NN*;

 int n,m,Time=,top=,scc=,ans;

 int dfn[NN],low[NN],instack[NN],q[NN],belong[NN],chu[NN];

 int cnt=,head[NN],next[MM],rea[MM],skt[NN];

 void add(int u,int v)

 {

     cnt++;

     next[cnt]=head[u];

     head[u]=cnt;

     rea[cnt]=v;

 }

 void tarjan(int u)

 {

     low[u]=dfn[u]=++Time;

     q[++top]=u,instack[u]=;

     for (int i=head[u];i!=-;i=next[i])

     {

         int v=rea[i];

         if (dfn[v]==)

         {

             tarjan(v);

             low[u]=min(low[v],low[u]);

         }

         else if (instack[v]) low[u]=min(low[u],dfn[v]);

     }

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

     {

         scc++;

         int x=-;

         while (x!=u)

         {

             x=q[top--];

             instack[x]=;

             belong[x]=scc;

             ++skt[scc];

         }

     }

 }

 void rebuild()

 {

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

     {

         for (int i=head[u];i!=-;i=next[i])

         {

             int v=rea[i];

             if (belong[u]!=belong[v]) chu[belong[u]]=;

         }

     }

     int num=,x=;

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

         if (chu[i]==) num++,x=i;

     if (num!=) ans=;

     else ans=skt[x];

     printf("%d",ans);

 }

 int main()

 {

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

     int x,y;

     memset(head,-,sizeof(head));

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

     {

         scanf("%d%d",&x,&y);

         add(x,y);

     }

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

         if (dfn[i]==) tarjan(i);

     rebuild();

 }