首页 > 代码库 > POJ2186

POJ2186

2024-08-29 14:55:44   223人阅读

poj2186 popular cows
 
Every cow‘s dream is to become the most popular cow in the herd. In a herd of N (1 <= N <= 10,000) cows, you are given up to M (1 <= M <= 50,000) ordered pairs of the form (A, B) that tell you that cow A thinks that cow B is popular. Since popularity is transitive, if A thinks B is popular and B thinks C is popular, then A will also think that C is 
popular, even if this is not explicitly specified by an ordered pair in the input. Your task is to compute the number of cows that are considered popular by every other cow. 

Input

* Line 1: Two space-separated integers, N and M 

* Lines 2..1+M: Two space-separated numbers A and B, meaning that A thinks B is popular. 

Output

* Line 1: A single integer that is the number of cows who are considered popular by every other cow. 

Sample Input

3 3
1 2
2 1
2 3

Sample Output

1

题意：10000头奶牛，50000对仰慕关系，且仰慕关系可以传递，问所有牛都仰慕的对象有多少？

————————————————————————————————————————————————

强连通分量中相互仰慕，所点后各点形成有向无环图，而其中如果有一个点（强连通分量）出度为0，那么这个强连通分量包含的点数就是答案；若果有多个点出度为0，则没有所有牛都仰慕的牛，答案0。

————————————————————————————————————————————————

技术分享 
  1 //poj2186 popular cows
  2 #include<cstdio>
  3 #include<iostream>
  4 #include<cstring>
  5 #include<algorithm>
  6 #include<stack>
  7 
  8 using namespace std;
  9 const int maxn=10010;
 10 const int maxm=50010;
 11 int n,m;
 12 struct edge
 13 {
 14     int u,v,next;
 15 }e[maxm],ee[maxm];
 16 int head[maxn],js,headd[maxn],jss;
 17 int dfsn[maxn],low[maxn],belong[maxn];
 18 bool ins[maxn];
 19 int sshu;
 20 int chudu[maxn],ss[maxn];
 21 stack<int>st;
 22 int visx;
 23 void init()
 24 {
 25     memset(head,0,sizeof(head));
 26     memset(e,0,sizeof(e));
 27     js=0;
 28     memset(headd,0,sizeof(headd));
 29     memset(ee,0,sizeof(ee));
 30     jss=0;
 31     memset(dfsn,-1,sizeof(dfsn));
 32     memset(low,-1,sizeof(low));
 33     sshu=0;
 34     memset(ss,0,sizeof(ss));
 35     while(!st.empty())st.pop();
 36     visx=0;
 37     memset(ins,0,sizeof(ins));
 38     memset(chudu,0,sizeof(chudu));
 39     memset(belong,0,sizeof(belong));
 40 }
 41 void addage(int u,int v,edge e[],int head[],int &js)
 42 {
 43     e[++js].u=u;e[js].v=v;
 44     e[js].next=head[u];head[u]=js;
 45 }
 46 
 47 void tarjan(int u)
 48 {
 49     dfsn[u]=low[u]=++visx;
 50     st.push(u);
 51     ins[u]=1;
 52     for(int i=head[u];i;i=e[i].next)
 53     {
 54         int v=e[i].v;
 55         if(dfsn[v]==-1)
 56         {
 57             tarjan(v);
 58             low[u]=min(low[u],low[v]);
 59         }
 60         else if(ins[v] && low[u]>dfsn[v])low[u]=dfsn[v];
 61     }
 62     if(low[u]==dfsn[u])
 63     {
 64         sshu++;
 65         int tp;
 66         do
 67         {
 68             tp=st.top();
 69             st.pop();
 70             ins[tp]=0;
 71             ss[sshu]++;
 72             belong[tp]=sshu;
 73         }while(u!=tp);
 74     }
 75 }
 76 int main()
 77 {
 78     while(scanf("%d%d",&n,&m)==2)
 79     {
 80         init();
 81         for(int i=0,u,v;i<m;i++)
 82         {
 83             scanf("%d%d",&u,&v);
 84             addage(u,v,e,head,js);
 85         }
 86         for(int i=1;i<=n;i++)
 87             if(dfsn[i]==-1)tarjan(i);
 88         for(int i=1;i<=m;i++)
 89         {
 90             int u=e[i].u,v=e[i].v;
 91             if(belong[u]!=belong[v])
 92             {
 93                 addage(belong[u],belong[v],ee,headd,jss);
 94                 chudu[belong[u]]++;
 95             }                
 96         }
 97         int count=0,mn;
 98         for(int i=1;i<=sshu;i++)
 99             if(chudu[i]==0)count++,mn=i;
100         if(count==1)printf("%d\n",ss[mn]);
101         else printf("0\n");
102     }
103     return 0;
104 }
View Code

 

POJ2186


联系
我们