Friday, December 30, 2016
UVa 10926 How many dependencies
UVa 10926 How many dependencies
#include <cstdio>
#include <iostream>
using namespace std;
#define init(n) { for (int i=0 ; i<=n ; i++) { visit[i] = false; for (int j=0 ; j<=n ; j++) adj[i][j] = adj[j][i] = false; } }
int n, dep[200], root[200], adj[200][200];
bool visit[200];
int dfs_visit(int s, int src) {
root[s] = src;
dep[s] = 0;
for (int i=1 ; i<=n ; i++) {
if (!visit[i] && adj[s][i]) {
visit[i] = true;
dep[s] += (dfs_visit(i,src)+1);
}
}
return dep[s];
}
void dfs() {
for (int i=1 ; i<=n ; i++) {
for (int j=0 ; j<=n ; j++) visit[j] = false;
dfs_visit(i,i);
}
}
int main( void ) {
int t, x, maxdepi, maxdep;
while (scanf("%d",&n)==1 && n) {
init(n);
for (int i=1 ; i<=n ; i++) {
scanf("%d",&t);
for (int j=0 ; j<t ; j++) {
scanf("%d",&x);
adj[i][x] = true;
}
}
dfs();
maxdep = -1000;
for (int i=1 ; i<=n ; i++) {
if (dep[i]>maxdep) {
maxdep = dep[i];
maxdepi = i;
}
}
printf("%d ",maxdepi);
}
return 0;
}
Go to link download
Labels:
10926,
dependencies,
how,
many,
uva