学步园

Description

Every cow's dream is to becomethe 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
istransitive, if A thinks B is popular and B thinks C is popular, then A willalso think that C is
popular, even if this is not explicitly specified by an ordered pair in theinput. Your task is to compute the number of cows that are considered popularby every other cow.

Input

* Line 1: Two space-separatedintegers, N and M

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

Output

* Line 1: A single integerthat 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

题目简介：（A,B）表示A认为B牛受欢迎，且每头牛都认为自己受欢迎。如果（A,B），且（B,C），则（A,C）。即A认为B受欢迎，B认为C受欢迎。那么A也认为C受欢迎。问题是，找出有多少头牛受所有牛的欢迎。

方法：Kosaraju算法。其实不是怎么懂。。。。。做这道题的时候是晚上了。做这道题的时候才学的这个算法。看这个算法看到两点多。。。。。算法是看懂了，但是还是不知道原理是什么。。。。。具体怎样的有待学习

#include<iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

vector<int> v1[10010], v2[10010];
vector<int> s;

int num[10010], sum[10010], mark[10010];
int counter;

void DFS1(int x)
{    
	mark[x] = 1;
	for (int i = 0; i < v1[x].size(); ++i)        
	{
		if (!mark[v1[x][i]])                
		{
			DFS1(v1[x][i]);                
		}
	}
	s.push_back(x);
};

void DFS2(int x)
{    
	num[x] = counter;  
	sum[counter]++; 
	mark[x] = 1;

	for (int i = 0; i < v2[x].size(); ++i)           
	{
		if (!mark[v2[x][i]])                   
		{
			DFS2(v2[x][i]);
		}
	}
};

void SUM(int n)
{    
	memset(mark, 0, sizeof(mark)); 
	for (int i = 1; i <= n; i++)    
	{
		for (int j = 0; j < v1[i].size();j++)        
		{
			int x = v1[i][j];            
			if (num[i] != num[x])
			{
				mark[num[i]] = 1;
			}
		}    
	}

	int flag = 0, ans;
	for (int i = 1; i <= counter; i++)
	{     
		if (!mark[i])       
		{
			ans = i;           
			flag++;       
		}
	}

	if (flag == 1)
	{
		printf("%d\n", sum[ans]);
	}
	else
	{
		printf("0\n");
	}
};

int main()
{
	int n, m, a, b, i, j;
	scanf("%d%d",&n,&m);
	for (i = 0;i<m;i++)
	{
		scanf("%d%d", &a, &b);
		v1[a].push_back(b);
		v2[b].push_back(a);
	}

	for (i = 1;i<=n;i++)
	{
		if (!mark[i])
		{
			DFS1(i);
		}
	}

	memset(mark, 0, sizeof(mark));

	counter = 0;
	for (i = s.size() - 1;i>=0;i--)
	{
		if (!mark[s[i]])
		{
			counter++;
			DFS2(s[i]);
		}
	}

	SUM(n);
	return 0;
}