bzoj1051: [HAOI2006]受欢迎的牛（强联通）

1051: [HAOI2006]受欢迎的牛

题目：传送门

题解：

　　 今天又做一道水题...

　　 强联通啊很明显

　　 水个模板之后统计一下每个强联通分量中点的个数，再统计一下出度...

　　 不难发现：缩点之后当且仅当仅有一个强联通分量的出度为0，那么这个强连通分量才可以被所有的点访问..

　　 具体的就自己画下图YY吧...

代码：

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #define qread(x) x=read()

 using namespace std;

 inline int read()

 {

     int f=,x=;char ch;

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return f*x;

 }

 struct node

 {

     int x,y,next;

 }a[];int len,last[];

 void ins(int x,int y)

 {

     len++;

     a[len].x=x;a[len].y=y;

     a[len].next=last[x];last[x]=len;

 }

 int n,m,id,tp,cnt;

 int belong[],dfn[],low[],sta[];

 bool v[];

 void dfs(int x)

 {

     low[x]=dfn[x]=++id;

     sta[++tp]=x;v[x]=true;

     for(int k=last[x];k;k=a[k].next)

     {

         int y=a[k].y;

         if(dfn[y]==-)

         {

             dfs(y);

             low[x]=min(low[x],low[y]);

         }

         else

         {

             if(v[y]==true)

                 low[x]=min(low[x],dfn[y]);

         }

     }

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

     {

         int i;cnt++;

         do{

             i=sta[tp--];

             v[i]=false;

             belong[i]=cnt;

         }while(i!=x);

     }

 }

 int num[],chu[];

 int main()

 {

     qread(n);qread(m);

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

     {

         int x,y;

         qread(x);qread(y);

         ins(x,y);

     }

     id=tp=cnt=;

     memset(dfn,-,sizeof(dfn));

     memset(low,,sizeof(low));

     memset(belong,,sizeof(belong));

     memset(v,false,sizeof(v));

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

         if(dfn[i]==-)

             dfs(i);

     if(cnt==){printf("%d\n",n);return ;}

     memset(num,,sizeof(num));

     memset(chu,,sizeof(chu));

     for(int i=;i<=n;i++)num[belong[i]]++;

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

         if(belong[a[i].x]!=belong[a[i].y])

             chu[belong[a[i].x]]++;

     int s=,k;

     for(int i=;i<=cnt;i++)if(chu[i]==){s++;k=i;}

     if(s==)printf("%d\n",num[k]);

     else printf("0\n");

     return ;

 }

又水一发...