Problem E

Spreading the News

In a large organization, everyone knows a lot of colleagues. However, friendship relations are kept with only a few of them, to whom news are told.

Suppose that whenever an employee knows of a piece of news, he tells it to all his friends on the following day. So, on the first day, the source of the information tells it to his friends; on the second day, the source's friends tell it to their friends; on the third day, the friends of the source's friends' tell it to their friends; and so on.

The goal is to determine:

·         the maximum daily boom size, which is the largest number of employees that, on a single day, hear the piece of news for the first time; and

·         the first boom day, which is the first day on which the maximum daily boom size occurs.

Problem

Write a program that, given the friendship relations between the employees and the source of a piece of news, computes the maximum daily boom size and the first boom day of that information spreading process.

Input

The first line of the input contains the number E of employees (1 <=E <=2500). Employees are numbered from 0 to E-1.

Each of the following E lines specifies the set of friends of an employee's (from employee 0 to employee E-1). A set of friends contains the number of friends N (0 <=N <15), followed by N distinct integers representing the employee's friends. All integers are separated by a single space.

The next line contains an integer T (1 <=T <60), which is the number of test cases.

Each of the following T lines contains an employee, which represents the (unique) source of the piece of news in the test case.

Output

The output consists of T lines, one for each test case.

If no employee (but the source) hears the piece of news, the output line contains the integer 0.

Otherwise, the output line contains two integers, M and D, separated by a single space, where M is the maximum daily boom size and D is the first boom day.

Sample Input

6

2 1 2

2 3 4

3 0 4 5

1 4

0

2 0 2

3

0

4

5

Sample Output

3 2

0

2 1

做法就利用 BFS, 逐漸擴散, 找出哪一次擴散最多人

#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int E, T, i, n, x;
    while(scanf("%d", &E) == 1) {
        vector<int> Link[E];
        for(i = 0; i < E; i++) {
            Link[i].clear();
            scanf("%d", &n);
            while(n--) {
                scanf("%d", &x);
                Link[i].push_back(x);
            }
        }
        scanf("%d", &T);
        while(T--) {
            scanf("%d", &x);
            int dp[E], used[E], cnt[E+1];
            memset(dp, 0, sizeof(dp));
            memset(cnt, 0, sizeof(cnt));
            memset(used, 0, sizeof(used));
            used[x] = 1;
            queue<int> Q;
            Q.push(x);
            while(!Q.empty()) {
                x = Q.front();
                Q.pop();
                for(vector<int>::iterator i = Link[x].begin(); i != Link[x].end(); i++) {
                    if(used[*i] == 0) {
                        used[*i] = 1;
                        Q.push(*i);
                        dp[*i] = dp[x]+1;
                        cnt[dp[*i]]++;
                    }
                }
            }
            int M = 0, D;
            for(i = 1; i <= E; i++) {
                if(cnt[i] > M) {
                    M = cnt[i];
                    D = i;
                }
            }
            if(M)
                printf("%d %d\n", M, D);
            else
                puts("0");
        }
    }
    return 0;
}