2013年7月31日

UVa 924 - Spreading The News

#include <cstdio>
#include <vector>
using namespace std;

int main() {
  int e;
  scanf("%d", &e);
  vector<int> knows[2500];
  for (int i = 0, n, id; i < e; i++) {
    scanf("%d", &n);
    while (n--) {
      scanf("%d", &id);
      knows[i].push_back(id);
    }
  }
  int t;
  scanf("%d", &t);
  while (t--) {
    int source;
    scanf("%d", &source);
    bool hear[2500] = {};
    hear[source] = true;
    vector<int> list;
    list.push_back(source);
    int day = 1, max = 0, ans = 0;
    while (list.size()) {
      vector<int> newList;
      for (int i = 0; i < list.size(); i++) {
        for (int j = 0; j < knows[list[i]].size(); j++) {
          int id = knows[list[i]][j];
          if (!hear[id]) {
            newList.push_back(id);
            hear[id] = true;
          }
        }
      }
      if (newList.size() > max) {
        max = newList.size();
        ans = day;
      }
      day++;
      list = newList;
    }
    if (max) {
      printf("%d %d\n", max, ans);
    } else {
      puts("0");
    }
  }
  return 0;
}

沒有留言:

張貼留言