POJ 2186 tarjan+缩点基础题

Popular Cows

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 37111		Accepted: 15124

Description

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

Sample Output

Hint

Cow 3 is the only cow of high popularity.

题意 n头牛 m个关系 a认为b受欢迎 b认为c受欢迎的话 a也认为c受欢迎问有多少头牛被其他所有人受欢迎

解析我们可以试着去分组把互相喜欢的人分到一组（组内可以喜欢其他人但组内人员必须互相喜欢，有向图任意两点相互可达）如果a组内一个人喜欢b组一个人的话那么就是a组的人都喜欢b组的所有人，但是,就不同时存在b组有人也喜欢a的人，因为如果存在的话a和b就是一个组了。然后我们就可以推出，当且仅当只有一个组x不喜欢其他组时有答案答案是这个组的大小否则输出0

强联通图缩点，再看下缩完点之后每个点的出度就好了。

  1 #include <stdio.h>
  2 #include <math.h>
  3 #include <string.h>
  4 #include <stdlib.h>
  5 #include <iostream>
  6 #include <sstream>
  7 #include <algorithm>
  8 #include <string>
  9 #include <queue>
 10 #include <map>
 11 #include <vector>
 12 #include <iomanip>
 13 using namespace std;
 14 const int maxn = 1e5+50;
 15 const int maxm = 1e4+10;
 16 const int inf = 0x3f3f3f3f;
 17 const double epx = 1e-10;
 18 typedef long long ll;
 19 const ll INF = 1e18;
 20 const double pi = acos(-1.0);
 21 int mp[maxn];
 22 struct node
 23 {
 24     int v,next;
 25 }edge[maxn];
 26 int dfn[maxn],low[maxn],index,visit[maxn],cnt,tot;
 27 int point[maxn];
 28 int heads[maxn],stack[maxn],num;
 29 void add(int x,int y)
 30 {
 31     edge[++cnt].next=heads[x];
 32     edge[cnt].v=y;
 33     heads[x]=cnt;
 34     return;
 35 }
 36 void tarjan(int x)
 37 {
 38     dfn[x]=low[x]=++tot;
 39     stack[++index]=x;
 40     visit[x]=1;
 41     for(int i=heads[x];i!=-1;i=edge[i].next)
 42     {
 43         if(!dfn[edge[i].v])
 44         {
 45             tarjan(edge[i].v);
 46             low[x]=min(low[x],low[edge[i].v]);
 47         }
 48         else if(visit[edge[i].v])
 49         {
 50             low[x]=min(low[x],dfn[edge[i].v]);
 51         }
 52     }
 53     if(low[x]==dfn[x])
 54     {
 55         do{
 56             int temp=stack[index];
 57             point[temp]=num;
 58             visit[temp]=0;
 59             index--;
 60         }while(x!=stack[index+1]);
 61         num++;
 62     }
 63     return;
 64 }
 65 int main()
 66 {
 67     int n,m;
 68     memset(heads,-1,sizeof(heads));
 69     memset(dfn,0,sizeof(dfn));
 70     memset(low,0,sizeof(low));
 71     memset(mp,0,sizeof(mp));
 72     scanf("%d%d",&n,&m);
 73     tot=cnt=num=index=0;
 74     for(int i=0;i<m;i++)
 75     {
 76         int u,v;
 77         scanf("%d%d",&u,&v);
 78         add(u,v);
 79     }
 80     for(int i=1;i<=n;i++)
 81         if(!dfn[i]) tarjan(i);
 82     int sum=0;
 83     for(int i=1;i<=n;i++)
 84     {
 85         for(int j=heads[i];j!=-1;j=edge[j].next)
 86         {
 87             if(point[i]!=point[edge[j].v])
 88             {
 89                 mp[point[i]]=1;
 90             }
 91         }
 92     }
 93     int cont=0,index;
 94     for(int i=0;i<num;i++)
 95         if(mp[i]==0)
 96         {
 97             cont++,index=i;
 98         }
 99     if(cont==1)
100     {
101         int ans=0;
102         for(int i=1;i<=n;i++)
103             if(point[i]==index)
104                 ans++;
105         cout<<ans<<endl;
106     }
107     else
108         cout<<"0"<<endl;
109     return 0;
110 }

View Code

http://blog.miskcoo.com/2016/07/tarjan-algorithm-strongly-connected-components

POJ 2186 tarjan+缩点 基础题

POJ 2186 tarjan+缩点基础题