Uva 924 Solution

#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;
}

Comments