POJ - 3660 Cow Contest（emmmm-spfa）

Cow Contest

Description

N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.

The contest is conducted in several head-to-head rounds, each between two cows. If cow A has a greater skill level than cow B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B), then cow A will always beat cow B.

Farmer John is trying to rank the cows by skill level. Given a list the results of M (1 ≤ M ≤ 4,500) two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.

Input

* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Each line contains two space-separated integers that describe the competitors and results (the first integer, A, is the winner) of a single round of competition: A and B

Output

* Line 1: A single integer representing the number of cows whose ranks can be determined
　

Sample Input

5 5
4 3
4 2
3 2
1 2
2 5

Sample Output

2

Source

USACO 2008 January Silver

                给你一些比赛结果，问你能确定名次的牛的数是多少~~；

                能够确定名次，就说明这头牛有间接打败关系的牛的数量+有间接被打败的牛的数量=n-1就好了；

               网上很多人用的是floyd算法直接n*3暴力求，确实代码简短，我也不再贴了，这里主要将领一个思路，用的是最短路的spfa的放法；时间复杂度低一些；

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
#define inf 0x3f3f3f3f
int n, m, cnt, ucnt;
int head[105];
int uhead[105];
int vis[105];
int d[105];
int ud[105];
struct ***
{
	int to, ne;
}ed[10005],ued[10005];
void init()
{
	for (int s = 1; s <= n; s++)
	{
		head[s] = -1;
		uhead[s] = -1;
	}
	cnt = 0;
}
void add(int from, int to)
{
	ed[cnt].to = to;
	ed[cnt].ne = head[from];
	head[from] = cnt++;
}
void uadd(int from, int to)
{
	ued[ucnt].to = to;
	ued[ucnt].ne = uhead[from];
	uhead[from] = ucnt++;
}
int spfa(int st, int d[],*** ed[],int head[])
{
	for (int s = 1; s <= n; s++)
	{
		d[s] = inf;
		vis[s] = 0;
	}
	queue<int>q;
	q.push(st);
	vis[st] = 1;
	d[st] = 0;
	while (!q.empty())
	{
		int t = q.front();
		q.pop();
		vis[t] = 0;
		for (int s = head[t]; ~s; s = ed[s].ne)
		{
			if (d[ed[s].to] != 0)
			{
				d[ed[s].to] = 0;
				if (!vis[ed[s].to])
				{
					vis[ed[s].to] = 1;
					q.push(ed[s].to);
				}
			}
		}
	}
	int sum = 0;
	for (int s = 1; s <= n; s++)
	{
		if (d[s] == 0)
		{
			sum++;
		}
	}
	return sum - 1;
}
int main()
{
	while (~scanf("%d%d", &n, &m))
	{
		init();
		while (m--)
		{
			int a, b;
			scanf("%d%d", &a, &b);
			add(a, b);
			uadd(b, a);
		}
		int sum = 0;
		for (int s = 1; s <= n; s++)
		{
			if (spfa(s, d, ed, head) + spfa(s, ud, ued, uhead) == n - 1)
			{
				sum++;
			}
		}
		printf("%d\n", sum);
	}
}