2013年9月2日

UVa 10926 - How Many Dependencies?

#include <cstdio>
#include <cstring>
#include <vector>
#define PB push_back
using namespace std;

int n;
vector<int> con[101];
bool vis[101];

void dfs(int i) {
  vis[i] = true;
  for (int j = 0; j < con[i].size(); j++) {
    if (!vis[con[i][j]]) {
      dfs(con[i][j]);
    }
  }
}

int main() {
  while (scanf("%d", &n) && n) {
    for (int i = 1; i <= n; i++) {
      con[i].clear();
      int num;
      scanf("%d", &num);
      while (num--) {
        int j;
        scanf("%d", &j);
        con[i].PB(j);
      }
    }
    int ans, maxDep = 0;
    for (int i = 1; i <= n; i++) {
      memset(vis, false, sizeof(vis));
      dfs(i);
      int dep = 0;
      for (int j = 1; j <= n; j++) {
        dep += vis[j];
      }
      if (dep > maxDep) {
        maxDep = dep;
        ans = i;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

沒有留言:

張貼留言