Wednesday, August 24, 2016

UVA 924 - Spreading The News- Solution

Unknown
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
class Graph{
   int V;
   list<int>*adj;
public:
    Graph(int V){this->V=V; adj=new list<int>[V];}
    ~Graph(){delete []adj;}
    void addEdge(int u,int v){ adj[u].pb(v);}
    void BFS(int s)
    {
        if (adj[s].size()==0) {printf("0\n"); return;}
        bool visited[V];
        memset(visited,false,sizeof(visited));
        int level[V];
        int cnt[V]={0};
        list<int>q;
        list<int>::iterator i;
        q.pb(s);
        visited[s]=true;
        level[s]=0;
        int d,m=0;
        while (!q.empty())
        {
            s=q.front();
            q.pop_front();
            cnt[level[s]]++;
            for (i=adj[s].begin();i!=adj[s].end();++i)
            {
                if (!visited[*i])
                {
                    q.pb(*i);
                    visited[*i]=true;
                    level[*i]=level[s]+1;
                }
            }
        }
        for (int j=1;j<=level[s];j++)
            if (m<cnt[j])
            {
                m=cnt[j];
                d=j;
            }
        printf("%d %d\n",m,d);
        return;
    }
};
int main()
{
    int e;
    while (scanf("%d",&e)!=EOF)
    {
        Graph g(e);
        int n,v;
        for (int i=0;i<e;i++)
        {
            scanf("%d",&n);
            while (n--)
            {
                scanf("%d",&v);
                g.addEdge(i,v);
            }
        }
        int t,s;
        scanf("%d",&t);
        while (t--)
        {
            scanf("%d",&s);
            g.BFS(s);
        }
    }
    return 0;
}

Unknown

Studying at Shahjalal University of Science and Technology, Sylhet.

0 comments:

Post a Comment

Coprights @ 2016,