首页 > 代码库 > HAOI2006 受欢迎的牛

HAOI2006 受欢迎的牛

HAOI2006 】受欢迎的牛

Description

每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛,给你M对整数(A,B),表示牛 A 认为牛 B受欢迎。这种关系是具有传递性的,如果A认为B受欢迎,B认为C受欢迎,那么牛A也认为牛C受欢迎。你的任务是求出有多少头牛被所有的牛认为是受欢迎的。

Input

第1行两个整数N,M;
接下来M行,每行两个数A,B,意思是A认为B是受欢迎的(给出的信息有可能重复,即有可能出现多个A,B)

Output

一个数,即有多少头牛被所有的牛认为是受欢迎的。

Sample Input

3 3

1 2

2 1

2 3

Sample Output

1

Hint

10%的数据N<=20,M<=50
30%的数据N<=1000,M<=20000
70%的数据N<=5000,M<=50000
100%的数据N<=10000,M<=50000

Source

HAOI2006
图论,连通性

 

本来寒假已经 AC 过一次,结果POJ数据增强了,结果 WA ,看不出哪里萎了,于是重新码了一遍。

思路还是很清晰的:tarjan 缩点成 DAG 然后判断是否只有一个强连通分量出度为 ,如果是,则输出size,否则输出 

证明:若强连通分量X有出边,则出边所指向的点必不喜欢X(若喜欢则与X为同一强连通分量),则X不是答案。存在两个或以上的强连通分量没有出边,则他们互相不喜欢,所以没有答案。

 

 

技术分享
  1 #include <map>
  2 #include <set>
  3 #include <cmath>
  4 #include <ctime>
  5 #include <queue>
  6 #include <stack>
  7 #include <cstdio>
  8 #include <string>
  9 #include <vector>
 10 #include <cstdlib>
 11 #include <cstring>
 12 #include <iostream>
 13 #include <algorithm>
 14 using namespace std;
 15 #define re register
 16 #define ll long long
 17 #define file(a) freopen(a".in","r",stdin); freopen(a".out","w",stdout);
 18 
 19 inline int gi()
 20 {
 21     bool b=0; int r=0; char c=getchar();
 22     while(c<0 || c>9) { if(c==-) b=!b; c=getchar(); }
 23     while(c>=0 && c<=9) { r=r*10+c-0; c=getchar(); }
 24     if(b) return -r; return r;
 25 }
 26 
 27 const int inf = 1e9+7, N = 1e4+7, M = 5e4+7;
 28 int n,m,num,f[N],dfn[N],low[N],cnt,siz[N],bl[N],hd[N],sum;
 29 bool b[N];
 30 struct node
 31 {
 32     int nx,to;
 33 }; node da[M],dd[M];
 34 stack <int> z;
 35 
 36 inline int Min (int a, int b)
 37 {
 38     return a < b? a : b;
 39 }
 40 
 41 inline void add (int fr, int to)
 42 {
 43     da[++num].to = to, da[num].nx = f[fr], f[fr] = num;
 44 }
 45 
 46 inline void link (int fr, int to)
 47 {
 48     dd[++sum].to = to, dd[sum].nx = hd[fr], hd[fr] = sum;
 49 }
 50 
 51 inline void tarjan (int o)
 52 {
 53     re int i,to;
 54     dfn[o] = low[o] = ++num;
 55     z.push(o); b[o] = 1;
 56     for (i=f[o]; i; i=da[i].nx)
 57         {
 58             to = da[i].to;
 59             if (!dfn[to])
 60                 {
 61                     tarjan (to); low[o] = Min (low[o], low[to]);
 62                 }
 63             else if (b[to]) low[o] = Min (low[o], dfn[to]);
 64         }
 65     if (dfn[o] == low[o])
 66         {
 67             ++cnt;
 68             do
 69                 {
 70                     to = z.top(); z.pop(); b[to] = 0;
 71                     bl[to] = cnt; siz[cnt]++;
 72                 }
 73             while (to != o);
 74         }
 75 }
 76 
 77 int main ()
 78 {
 79     n = gi(), m = gi();
 80     re int i,j,to,x,y,ans=0; bool fg;
 81     for (i=1; i<=m; i++)
 82         {
 83             x = gi(), y = gi();
 84             add (x, y);
 85         }
 86     num = 0;
 87     for (i=1; i<=n; i++) if(!dfn[i]) tarjan(i);
 88     for (i=1; i<=n; i++)
 89         for (j=f[i]; j; j=da[j].nx)
 90             {
 91                 to = da[j].to; x = bl[i]; y = bl[to];
 92                 if (x != y) link (x, y);
 93             }
 94     for (i=1; i<=cnt; i++)
 95         {
 96             fg = 1;
 97             for (j=hd[i]; j; j=dd[j].nx) if (dd[j].to != i) fg = 0;
 98             if (fg)
 99                 {
100                     if(!ans) ans = siz[i];
101                     else
102                         {
103                             puts ("0");
104                             return 0;
105                         }
106                 }
107         }
108     printf ("%d\n",ans);
109     return 0;
110 }
View Code

 

HAOI2006 受欢迎的牛