#include<bits/stdc++.h>
#define White 1
#define Black 2
#define N 2510
using namespace std;
int node, a[N][N], color[N], distances[N], levelcount[N];
void bfs(int startnode)
{
for(int i=0;i<node;i++)
{
color[i] = White;
distances[i] = -1;
levelcount[i] = 0;
}
color[startnode] = Black;
distances[startnode] = 0;
levelcount[startnode] = 0;
queue<int>q;
q.push(startnode);
while(!q.empty())
{
int x = q.front();
q.pop();
for(int i=0;i<node;i++)
{
if(a[x][i] == 1 && color[i] == White)
{
color[i] = Black;
distances[i] = distances[x] + 1;
int l = distances[i];
levelcount[l] += 1;
q.push(i);
}
}
}
int mx = -1, level;
for(int i=0;i<node;i++)
{
if(mx < levelcount[i])
{
mx = levelcount[i];
level = i;
}
}
if(mx)
cout << mx << " " << level << "\n";
else
cout << 0 << "\n";
}
int main()
{
int edge, i, j, node1, t;
cin >> node;
for(i=0;i<node;i++)
{
cin >> edge;
for(j=1;j<=edge;j++)
{
cin >> node1;
a[i][node1] = 1;
}
}
cin >> t;
for(i=1;i<=t;i++)
{
cin >> node1;
bfs(node1);
}
return 0;
}
#define White 1
#define Black 2
#define N 2510
using namespace std;
int node, a[N][N], color[N], distances[N], levelcount[N];
void bfs(int startnode)
{
for(int i=0;i<node;i++)
{
color[i] = White;
distances[i] = -1;
levelcount[i] = 0;
}
color[startnode] = Black;
distances[startnode] = 0;
levelcount[startnode] = 0;
queue<int>q;
q.push(startnode);
while(!q.empty())
{
int x = q.front();
q.pop();
for(int i=0;i<node;i++)
{
if(a[x][i] == 1 && color[i] == White)
{
color[i] = Black;
distances[i] = distances[x] + 1;
int l = distances[i];
levelcount[l] += 1;
q.push(i);
}
}
}
int mx = -1, level;
for(int i=0;i<node;i++)
{
if(mx < levelcount[i])
{
mx = levelcount[i];
level = i;
}
}
if(mx)
cout << mx << " " << level << "\n";
else
cout << 0 << "\n";
}
int main()
{
int edge, i, j, node1, t;
cin >> node;
for(i=0;i<node;i++)
{
cin >> edge;
for(j=1;j<=edge;j++)
{
cin >> node1;
a[i][node1] = 1;
}
}
cin >> t;
for(i=1;i<=t;i++)
{
cin >> node1;
bfs(node1);
}
return 0;
}
Comments
Post a Comment