UVa – 10926 – How Many Dependencies?


#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

int dist[101][101];

int main() {

	for (int N, max_deps = 0, max_i = 0; scanf("%d", &N) && N; max_deps = 0, max_i = 0) {
		memset(dist, 0, sizeof dist);
		
		for (int T, n = 1; n <= N && scanf("%d", &T); n++)
			for (int t = 1, o; t <= T && scanf("%d", &o); t++)
				dist[n][o] = 1;

		for (int k = 1; k <= N; k++)
			for (int i = 1; i <= N; i++)
				for (int j = 1; j <= N; j++)
					if ((dist[i][k] * dist[k][j] != 0) && (i != j) && dist[i][k] + dist[k][j] >= dist[i][j]) {
						dist[i][j] = dist[i][k] + dist[k][j];
						if (dist[i][j] > max_deps || (dist[i][j] == max_deps && i < max_i))
							max_i = i, max_deps = dist[i][j];
					}

		printf("%d\n", max_i);
	}
	return 0;
}
Advertisements

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

%d bloggers like this: