uva: Cow Contest ( Floyd Warshall – Transitive Closure)

Cow Contest

 

Problem :

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

The input contains multiple test cases, until the end of file. Each test case is given in the following order:

  • 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

For each test case, output in a single line, a single integer representing the number of cows whose ranks can be determined.

 

 

Solution analysis:

 

 C++ Solution:


#include <stdio.h>
#define NMAX 100

int beating[NMAX+1][NMAX+1];

int main()
{
	int m,n,i,j,k,result;

	while(EOF != scanf("%d %d", &n, &m))
	{

		for(i=0; i < n; i++)
		{
			for(j=0; j < n; j++)
			{
				beating[i][j] = 0;
			}
			beating[i][i] = 1;
		}

		while(m--)
		{
			scanf("%d %d",&i,&j);
			beating[--i][--j] = 1;
		}

	for(k=0; k < n; k++)
		for(i=0; i< n; i++)
			for(j=0; j < n; j++)
			{
				if( beating[i][k] &&  beating[k][j] )
				{
					beating[i][j] = 1;
				}
			}

	result = 0;
	for(i=0;i < n ; i++)
	{
		int nReachable=0;

		for(j=0; j < n; j++)
		{
			nReachable+= beating[i][j] + beating[j][i];
		}

		if(nReachable == n+1 ) result++;
	}

		printf("%d\n", result);
	}

	return 0;
}

 

 

Sample Input

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

Sample Output

2

Advertisements

About M Moniruzzaman
A passionate software engineer, have been developing applications on various platforms such as Android, iPhone, .Net (C#) technologies and web based ASP.NET, PHP, JavaScript, jQuery technologies for more than 10 years. Especially I have expertise on developing applications for Android and iPhone, as well as service oriented, client-server based applications where clients will be reside on Android/iPhone that communicate with WCF(.NET) service hosted on server. I have completed certification in Microsoft Certified Professional Developer (MCPD) on .Net 4 . I have completed my graduation in -- B.Sc. (Engineering) in Computer Science and Engineering, ShahJalal University of Science and Technology, Bangladesh. Thanks, M. Moniruzzaman (Zaman)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: