BZOJ难得的水题（其实是HA太弱了）

原题：

每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，给你M对整数(A,B)，表示牛A认为牛B受欢迎。 这

种关系是具有传递性的，如果A认为B受欢迎，B认为C受欢迎，那么牛A也认为牛C受欢迎。你的任务是求出有多少头

牛被所有的牛认为是受欢迎的。

N<=10000,M<=50000

 

求强连通分量，缩点，搞成DAG，唯一一个出度为0的点就是答案

为什么呐

缩点后每个强连通块内部肯定是能互相到达的，而且强连通块是DAG没有环，所以如果整个DAG是连通的，那么唯一一个出度为零的强连通块一定会被其他所有强连通块覆盖（因为图是连通的而且没有环）

（似乎涉及到覆盖问题都可以用缩点搞）

需要注意的问题：

1.注意图不一定连通！！！

2.需要判断DAG是否连通，如果有多个点出度为0，答案就是0，因为这样子就没有任何一个强连通块能被其他所有强连通块覆盖

画图模拟很好理解

这题在BZOJ上WA了好几遍，全是低级错误，代码能力还要再提升

代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 int read(){
    int z=0,mark=1;  char ch=getchar(); 8     while(ch<'0'||ch>'9'){
    if(ch=='-')mark=-1;  ch=getchar();} 9     while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0';  ch=getchar();}10     return z*mark;11 }12 struct ddd{
    int next,y;}e[51000];int LINK[11000],ltop=0;13 inline void insert(int x,int y){e[++ltop].next=LINK[x];LINK[x]=ltop;e[ltop].y=y;}14 ddd DAG[11000];  int DLINK[51000],Dltop=0;  int Dcd[11000];15 inline void Dinsert(int x,int y){DAG[++Dltop].next=DLINK[x];DLINK[x]=Dltop;DAG[Dltop].y=y;  Dcd[x]++;}16 int n,m;17 int low[11000],dfn[11000],bu=0;18 int zhan[1100000],top=0;19 bool visited[11000];20 int group[11000],id=0;21 int ge[11000];22 void Tarjian(int x){23     zhan[++top]=x;  visited[x]=true;24     low[x]=dfn[x]=++bu;25     for(int i=LINK[x];i;i=e[i].next){26         if(!dfn[e[i].y]){27             Tarjian(e[i].y);28             low[x]=min(low[x],low[e[i].y]);29         }30         else if(visited[e[i].y])31             low[x]=min(low[x],dfn[e[i].y]);32     }33     if(dfn[x]==low[x]){34         id++;35         int temp;36         do{37             temp=zhan[top--];38             visited[temp]=false;39             group[temp]=id;40             ge[id]++;41         }while(temp!=x);42     }43 }44 void get_DAG(){45     for(int i=1;i<=n;i++)46         for(int j=LINK[i];j;j=e[j].next)47             if(group[i]!=group[e[j].y])48                 Dinsert(group[i],group[e[j].y]);49 }50 int main(){
    //freopen("ddd.in","r",stdin);51     memset(visited,0,sizeof(visited));52     memset(dfn,0,sizeof(dfn));53     memset(ge,0,sizeof(ge));54     cin>>n>>m;55     int _left,_right;56     while(m --> 0){
    //趋向于57         _left=read();  _right=read();58         insert(_left,_right);59     }60     for(int i=1;i<=n;i++)if(!dfn[i])  Tarjian(i);//注意图不一定连通！！！61     get_DAG();62     int temp=0;63     for(int i=1;i<=id;i++)if(Dcd[i]==0){64         if(temp){  temp=0;  break;}//防止DAG不连通，这样子就没有任何一个强连通块能被其他所有强连通块覆盖65         else  temp=i;66     }67     cout<
           
            <