UVa 615 - Is It A Tree?

// UVa 615 - Is It A Tree?

#include <iostream>
#include <stdio.h>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

#define integer signed long long int

map<integer, vector<integer> > lnk;
integer c;
map<integer, bool> taken;

void dfs(integer i) {
	c++;
	taken[i] = true;
	for (int j = 0; j < lnk[i].size(); j++)
		if (!taken[lnk[i][j]]) {
			dfs(lnk[i][j]);
		}
}

int main() {
	integer a, b;
	int t = 0;
	while ((cin >> a >> b) && a >= 0 && b >= 0) {
		map<integer, integer> parents;
		bool empty = true;
		lnk.clear();
		while (a != 0 && b != 0) {
			empty = false;
			parents[b]++;
			parents[a] = parents[a];
			lnk[a].push_back(b);
			cin >> a >> b;
		}
		bool tree = true;
		integer roots = 0;
		for (map<integer, integer>::const_iterator I = parents.begin(); I != parents.end(); I++) {
			if (I->second == 0) {
				roots++;
				if (roots > 1) {
					tree = false;
					break;
				} else {
					c = 0;
					taken.clear();
					dfs(I->first);
				}
			} else if (I->second > 1) {
				tree = false;
				break;
			}
		}
		t++;
		if (empty || (tree && (roots == 1) && c == parents.size()))
			printf("Case %d is a tree.\n", t);
		else
			printf("Case %d is not a tree.\n", t);
	}
	return 0;
}