UVa: 615 (Is It A Tree?)


Critical Cases

// collected test cases 
1 2
1 2
0 0
Case 1 is not a tree.
0 0
Case 2 is a tree.
1 2 
2 1
0 0
Case 3 is not a tree.
10006 10008 10005 10003  10005 10002 10006 10004
10005 10006  0 0
Case 4 is a tree.
-5 -6

// http://uva.onlinejudge.org/external/6/615.html
// Runtime: 0.016s
// tag: Connected Graph, DFS, inDegree


//============================================================================
// Name        : SampleUVa.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <map>

#define N 1000
using namespace std;

map <int, int> mapping;
vector <int> matrix [N];
map <int, int> inDegree;
bool visited [N];

void dfs (int n)
{
	visited [n] = true;

	for ( size_t i = 0; i < matrix [n].size (); i++ ) {
		if ( visited [matrix [n] [i]] == false ) dfs (matrix [n] [i]);
	}
}

void print ()
{
	for ( map<int,int>::iterator it = inDegree.begin (); it != inDegree.end (); it++) {
		printf ("# %d ==> %d ||", (*it).first, (*it).second);
	}

	printf ("\n");
}

int main ()
{

	int m, n;
	int cases = 0;

	while ( scanf ("%d %d", &m, &n) ) {
		if ( m < 0 && n < 0 ) break;

		mapping.clear ();
		inDegree.clear ();
		for ( int i = 0; i < N; i++ ) matrix [i].clear ();
		memset (visited, false, sizeof visited);
		int mappingNum = 1;

		mapping [m] = mappingNum++;
		mapping [n] = mappingNum++;

		matrix [mapping [m]].push_back (mapping [n]);
		inDegree [mapping [m]] = inDegree [mapping [n]] = 0;
		inDegree [mapping [n]]++;

		//print ();

		if ( m == 0 && n == 0 ) { printf ("Case %d is a tree.\n", ++cases); continue; }

		while ( scanf ("%d %d", &m, &n) ) {
			if ( m == 0 && n == 0 ) break;

			if ( !mapping [m] ) { mapping [m] = mappingNum++; inDegree [mapping [m]] = 0; }
			if ( !mapping [n] ) { mapping [n] = mappingNum++;  inDegree [mapping [n]] = 0; }

			matrix [mapping [m]].push_back (mapping [n]);
			inDegree [mapping [n]]++;
			//print ();
		}

		int root;
		int rootCount = 0;
		bool isOnlyOneInDegree = true;

		for ( map<int,int>::iterator it = inDegree.begin (); it != inDegree.end (); it++) {
			if ( (*it).second == 0 ) { rootCount++;
			//printf ("*** %d\n", (*it).first);
			root = (*it).first; }
			else if ( (*it).second > 1 ) isOnlyOneInDegree = false;
		}

		printf ("Case %d is ", ++cases);

		if ( rootCount > 1 || !isOnlyOneInDegree || rootCount == 0 ) { printf ("not a tree.\n"); continue; }

		dfs (root);

		bool isConnectedGraph = true;

		for ( int i = 1; i < mappingNum; i++ ) {
			if ( visited [i] == false ) isConnectedGraph = false;
		}

		if ( !isConnectedGraph ) printf ("not a tree.\n");
		else printf ("a tree.\n");

	}

	return 0;
}
Advertisements

One thought on “UVa: 615 (Is It A Tree?)

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s