Tuesday, October 20, 2015

UVa 10926 - How Many Dependencies?

//UVa 10926 - How Many Dependencies?
#include <iostream>
#include <string.h>
using namespace std;

int adj[101][101];
int n;
bool yet[101];

int dfs(int i) {
	yet[i] = false;
	int c = 1;
	for (int j = 1; j <= adj[i][0]; j++)
		if (yet[adj[i][j]])
			c += dfs(adj[i][j]);
	return c;
}

int main() {
	for (cin >> n; n; cin >> n) {
		for (int i = 1; i <= n; i++) {
			cin >> adj[i][0];
			for (int j = 1; j <= adj[i][0]; j++)
				cin >> adj[i][j];
		}
		int sc = 0, si;
		for (int i = 1; i <= n; i++) {
			memset(yet, true, sizeof(yet));
			int c = dfs(i);
			if (c > sc) {
				sc = c;
				si = i;
			}
		}
		cout << si << endl;
	}
	return 0;
}

No comments:

Post a Comment