poj——Popular Cows
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 33840 | Accepted: 13789 |
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
3 31 22 12 3
Sample Output
1
Hint
Cow 3 is the only cow of high popularity.
Source
题目大意：
有N(N<=10000)头牛，每头牛都想成为most popular的牛，给出M(M<=50000)个关系，如(1,2)代表1欢迎2，关系可以传递，但是不可以相互，即1欢迎2不代表2欢迎1，但是如果2也欢迎3那么1也欢迎3.
给出N,M和M个欢迎关系，求被所有牛都欢迎的牛的数量。
思路：
这道题和刻录光盘的思路是一样的，我们先找这个图中的强连通分量，然后缩点，然后判断出读为0的点的个数。
我们可以这样想：如果一个点的出度为零，这样的话这个点是不是一定不会喜欢别的牛？！
【在这往后提的每个牛的出度均为缩点后的出度】
如果有两个（及两个以上）的牛都不喜欢别的牛的话，那么是不是说明这群牛一定不会有每个牛都喜欢？
这样的话，是不是就没有符合上述条件的牛，那就输出0
如果是只有一个牛的出度为零，是不是就说明这些牛一定有被所有牛都喜欢的。
被所有牛都喜欢的牛的个数为：出度为零的强连通分量中点的个数。
如图：
代码：
#include#include #include #include #include #define N 90000using namespace std;bool vis[N];int n,m,x,y,s,ans,sum,tat,top,tim;int out[N],head[N],dfn[N],low[N],stack[N],col[N],point[N];inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f;}struct Edge{ int from,next,to; }edge[N];inline int add(int x,int y){ tat++; edge[tat].to=y; edge[tat].next=head[x]; head[x]=tat;}inline void tarjan(int now){ dfn[now]=low[now]=++tim; stack[++top]=now; vis[now]=1; for(int i=head[now];i;i=edge[i].next) { int t=edge[i].to; if(vis[t]) low[now]=min(low[now],dfn[t]); else if(!dfn[t]) { tarjan(t); low[now]=min(low[now],low[t]); } } if(low[now]==dfn[now]) { sum++;col[now]=sum;point[sum]++; for(;stack[top]!=now;top--) { point[sum]++; col[stack[top]]=sum; vis[stack[top]]=0; } vis[now]=0;top--; }}inline void shrink_point(){ for(int i=1;i<=n;i++) for(int j=head[i];j;j=edge[j].next) if(col[i]!=col[edge[j].to]) out[col[i]]++;}int main(){ n=read(),m=read(); for(int i=1;i<=m;i++) x=read(),y=read(),add(x,y); for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); shrink_point(); for(int i=1;i<=sum;i++) if(!out[i]) ans++,s=point[i]; if(ans!=1) s=0; printf("%d",s); return 0;}