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