首页 > > 程序设计 > C/C++ >

P2341 [HAOI2006]受欢迎的牛

2018-06-17 22:15:31来源：未知阅读 ()

题目描述

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶

牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜

欢B，B喜欢C，那么A也喜欢C。牛栏里共有N 头奶牛，给定一些奶牛之间的爱慕关系，请你

算出有多少头奶牛可以当明星。

输入输出格式

输入格式：

? 第一行：两个用空格分开的整数：N和M

? 第二行到第M + 1行：每行两个用空格分开的整数：A和B，表示A喜欢B

输出格式：

? 第一行：单独一个整数，表示明星奶牛的数量

输入输出样例

输入样例#1：

输出样例#1：

说明

只有 3 号奶牛可以做明星

【数据范围】

10%的数据N<=20, M<=50

30%的数据N<=1000,M<=20000

70%的数据N<=5000,M<=50000

100%的数据N<=10000,M<=50000

tarjan缩点，

当一个点的出度为0是，他们是明星、

当有两个及以上的店出度为0是，他们不可能相互喜欢，所以没有明星。

这里有个小技巧，

我们反向加边，就把求出度的问题改为了求入度的问题

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<algorithm>
  6 #include<queue>
  7 #include<stack>
  8 using namespace std;
  9 const int MAXN=500001;
 10 static void read(int &n)
 11 {
 12     char c='+';int x=0;bool flag=0;
 13     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
 14     while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c-48);c=getchar();}
 15     flag==1?n=-x:n=x;
 16 }
 17 struct node
 18 {
 19     int u,v,nxt;
 20 }edge[MAXN];
 21 int head[MAXN];
 22 int num=1;
 23 void add_edge(int x,int y)
 24 {
 25     edge[num].u=x;
 26     edge[num].v=y;
 27     edge[num].nxt=head[x];
 28     head[x]=num++;
 29 }
 30 int dfn[MAXN];
 31 int low[MAXN];
 32 int tot=0;
 33 int vis[MAXN];
 34 int color[MAXN];
 35 int colornum;
 36 int happen[MAXN];
 37 stack<int>s;
 38 void tarjan(int now)
 39 {
 40     dfn[now]=low[now]=++tot;
 41     vis[now]=1;
 42     s.push(now);
 43     for(int i=head[now];i!=-1;i=edge[i].nxt)
 44     {
 45         if(!dfn[edge[i].v])
 46         {
 47             tarjan(edge[i].v);
 48             low[now]=min(low[now],low[edge[i].v]);
 49         }
 50         else if(vis[edge[i].v])// 公共祖先 
 51         {
 52             low[now]=min(low[now],dfn[edge[i].v]);
 53         }
 54     }
 55     if(dfn[now]==low[now])// root
 56     {
 57         colornum++;
 58         while(now!=s.top())
 59         {
 60             if(!color[s.top()])
 61             color[s.top()]=colornum;
 62             happen[color[s.top()]]++;
 63             vis[s.top()]=0;
 64             s.pop();
 65         }
 66         if(!color[s.top()])
 67         color[s.top()]=colornum;
 68         happen[color[s.top()]]++;
 69         vis[s.top()]=0;
 70         s.pop();
 71     }
 72 }
 73 int main()
 74 {
 75 //    freopen("cow.in","r",stdin);
 76 //    freopen("cow.out","w",stdout);
 77     int n,m;
 78     memset(head,-1,sizeof(head));
 79     read(n);read(m);
 80     for(int i=1;i<=m;i++)
 81     {
 82         int x,y;
 83         read(x);read(y);
 84         add_edge(y,x);
 85     }
 86     
 87     for(int i=1;i<=n;i++)
 88         if(!dfn[i])
 89             tarjan(i);
 90    // for(int i=1;i<=n;i++)
 91     //    happen[color[i]]++;
 92     memset(vis,0,sizeof(vis));
 93     for(int i=1;i<=n;i++)
 94         for(int j=head[i];j!=-1;j=edge[j].nxt)
 95             if(color[edge[j].u]!=color[edge[j].v])
 96                 vis[color[edge[j].v]]++;
 97     int ans=0;
 98     for(int i=1;i<=colornum;i++)
 99     if(!vis[i])
100         {
101             if(ans)
102             {
103                 printf("0\n");
104                 return 0;
105             }
106             else ans=happen[i];
107         }
108     printf("%d",ans);
109     return 0;
110 }