Saturday, June 13, 2015

UVa 10000 - Longest Paths

// UVa 10000 - Longest Paths
#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>
using namespace std;

int main() {
	int n;
	int t = 0;
	while ((cin >> n) && n) {
		t++;
		int s;
		cin >> s;
		bool lnk[101][101];
		memset(lnk, false, sizeof(lnk));
		int parents[101];
		memset(parents, 0, sizeof(parents));
		int p, o;
		while (cin >> p >> o && p && o) {
			lnk[p][o] = true;
			parents[o]++;
		}
		int lvl[101];
		memset(lvl, 255, sizeof(lvl));
		queue<int> q;
		q.push(s);
		lvl[s] = 0;
		int sol = s;
		while (!q.empty()) {
			int m = q.front();
			q.pop();
			for (int i = 1; i <= n; i++)
				if (lnk[m][i]) {
					parents[i]--;
					if (lvl[i] < lvl[m] + 1) {
						lvl[i] = lvl[m] + 1;
						q.push(i);
						if (lvl[sol] < lvl[i] || lvl[sol] == lvl[i] && i < sol)
							sol = i;
					}
				}
		}
		printf("Case %d: The longest path from ", t);
		printf("%d has length %d, finishing at %d.\n\n", s, lvl[sol], sol);
	}
	return 0;
}

No comments:

Post a Comment