首页 > 代码库 > P2341 [HAOI2006]受欢迎的牛(tarjan+缩点)

P2341 [HAOI2006]受欢迎的牛(tarjan+缩点)

P2341 [HAOI2006]受欢迎的牛

题目描述

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

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

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

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

输入输出格式

输入格式:

 

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

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

 

输出格式:

 

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

 

输入输出样例

输入样例#1:
3 31 22 12 3
输出样例#1:
1

说明

只有 3 号奶牛可以做明星

【数据范围】

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

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

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

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

 

分析:只有所有奶牛都喜欢的奶牛才可能成为明星,也就是所有的点都能到达的点。

首先可以求强联通分量,然后统计所有强联通分量的出度,如果为0的只有一个,输出这个强联通分量的大小即可,否则输出0

为啥呢,因为我们所要求得点是所有点都能达到(被所有牛认同的牛),所以可以先tarjan缩点(求的点有多个),缩点之后,点内所有的点是可以相互支持的,可以不用管他们,看做一个点即可。然后为啥找出度为0的且只能找一个呢?1、首先他必出度为0,如果他有出度,设他支持a,这已经是有个大点(缩点)了,大点内所有的点都可以相互支持,然后大点又支持a(a不在大点内),且a一定不支持这个大点(如果a支持大点,a在这个大点(被缩点)内),所以一定要找没有出度的点;2、只能找一个,如果有两个或以上,那么就一个明星也没有,我们假设两个点x,y没有出度,既然x,y都没有出度,x点就不支持y,y也不支持x,所以就没有没有明星,(一个出度为零的点无法到达另一个出度为零的点,都没有出度了,哪来的“到达”呢?)

 

 1 #include<cstdio> 2 #include<algorithm> 3 #include<stack> 4 using namespace std; 5  6 const int MAXN = 10100; 7 struct Edge{ 8     int to,nxt; 9 }e[100100];10 int head[MAXN],dfn[MAXN],low[MAXN],bel[MAXN],sz[MAXN],pd[MAXN],x[50010],y[50010];11 bool vis[MAXN];12 int cnt,n,m,tot,num,ans,flag;13 stack<int>s;14 15 void add(int u,int v)16 {17     ++cnt;18     e[cnt].to = v;19     e[cnt].nxt = head[u];20     head[u] = cnt;21 }22 void tarjan(int u)23 {24     low[u] = dfn[u] = ++tot;25     s.push(u);26     vis[u] = true ;27     for (int i=head[u]; i; i=e[i].nxt)28     {29         int v = e[i].to;30         if (!dfn[v])31         {32             tarjan(v);33             low[u] = min(low[u],low[v]);34         }35         else if (vis[v]) low[u] = min(low[u],low[v]);36     }37     if (dfn[u]==low[u])38     {39         int now = -1;40         num++;41         while (now!=u)42         {43             now = s.top();44             s.pop();45             bel[now] = num;46             sz[num]++;47             vis[now] = false ;48         }49     }50 }51 int main()52 {53     scanf("%d%d",&n,&m);54     for (int i=1; i<=m; ++i)55     {56         scanf("%d%d",&x[i],&y[i]);57         add(x[i],y[i]);58     }59     for (int i=1; i<=n; ++i)60         if (!dfn[i]) tarjan(i);61     62     for (int i=1; i<=m; ++i)63         if (bel[x[i]]!=bel[y[i]])64             pd[bel[x[i]]]++;65     66     for (int i=1; i<=num; ++i)67         if (!pd[i])68             flag++, ans = sz[i];69             70     if (flag==1) printf("%d",ans);71     else printf("0");72     return 0;73 }

 

P2341 [HAOI2006]受欢迎的牛(tarjan+缩点)