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 3 1 2 2 1 2 3Sample Output
1Hint
Cow 3 is the only cow of high popularity.Source
USACO 2003 Fall题意：如果A牛认为B牛受欢迎，那B牛是受欢迎的，如果B认为C是欢迎的，那么A也认为C是受欢迎的，现在求如果有牛被所有的牛都认为是受欢迎的，那么就是最受欢迎的。换言之，就是求出度为0的个数，如果是一个，那么就输出原图中缩为这个点的个数，如果不是一个，那么就不可能有牛是最受欢迎的牛。
AC代码：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <stack> using namespace std; #define MAX 100005 #define MAXN 500005 struct Edge { int u; int v; int next; } edge[MAXN]; int DFN[MAX], low[MAX], in[MAX], out[MAX]; int flag[MAX], step[MAX], head[MAX]; int sum[MAX]; stack<int>S; int res, tot, M, ans, ans1, N; void Init() { memset(DFN, 0, sizeof(DFN)); memset(low, 0, sizeof(low)); memset(in, 0, sizeof(in)); memset(out, 0, sizeof(out)); memset(flag, 0, sizeof(flag)); memset(head, -1, sizeof(head)); memset(sum, 0, sizeof(sum)); memset(edge, 0, sizeof(edge)); memset(step, 0, sizeof(step)); if(!S.empty()) S.pop(); tot = 0, res = 0; } void addedge(int u, int v, int k) { edge[k].u = u, edge[k].v = v, edge[k].next = head[u], head[u] = k; } void tarjan(int u) { DFN[u] = low[u] = ++tot; flag[u] = 1; S.push(u); for(int j = head[u]; j != -1; j = edge[j].next) ///更新low值 { int v = edge[j].v; if(!DFN[v]) { tarjan(v); low[u] = min(low[u],low[v]); } else if(flag[v]) { low[u] = min(low[u],low[v]); } } int v; if(DFN[u]==low[u]) ///缩点 { do { v = S.top(); S.pop(); step[v] = res; sum[res]++; flag[v] = 0; } while(u!=v); res++; } } void solve() { for(int i=0; i<N; i++) for(int j=head[i]; j!=-1; j=edge[j].next) ///统计缩点后的各点的出度 { if(step[i]!=step[edge[j].v]) out[step[i]]++; } int f, yy=0; for(int i = 0; i < res; i++) { //printf("out = %d\n",out[i]); if(!out[i]) { yy++; f = i; //printf("yy = %d f = %d\n",yy,i); } } if(yy==1) printf("%d\n",sum[f]); else printf("0\n"); } int main() { while(~scanf("%d%d",&N,&M)) { Init(); for(int i = 0; i < M; i++) { int a, b; scanf("%d%d",&a,&b); addedge(a-1,b-1,i); ///建图 } for(int i = 0; i < N; i++) { if(!DFN[i]) { tarjan(i); } } solve(); } return 0; }
