UVa - 567 ( Risk Solution )

Try Yourself First. For help Scroll Down .

Tip : The toughest thing in this problem is to understand the Input Specification .Here the problem says to find the minimum number of country you have to win to go from a SOURCE to DESTINATION . This line clearly means a Normal BFS problem . So the INPUT SPECIFICATION . Huh ? It says we can take a total of 20 lines . From which 19 lines are the Graph Specification and 20th line are the query line we have to check out . So............. Check this Points given below .

Point 1 : The 1st line means 1st node , the 2nd node means the 2nd..... the 19th line means 19th node .

Point 2 : The 1st number of each line denotes how many nodes with connected the each node.If

              1st line contains 2 3 7 that means Node 1 is connected to TWO nodes.Those are 3 & 7.

              2nd line contains 3 2 8 9 that means Node 2 connected to THREE nodes.Those are 2, 8 & 9.

Hope You Got It . 

Point 3 : Now for each Query Manipulate the BFS and Find Minimum Country to win . Don't forget to clear  your GRAPH after completing A TEST SET . Give a special Care to the Output Formation . Otherwise you will get PRESENTATION ERROR . Go to Code Now .

Code :

#include<bits/stdc++.h>

using namespace std;

vector<int>graph[21];

void bfs(int s, int d)

{

    queue< int >q;

    int visited[50]={0}, level[50];

    visited[s]=1;

    level[s]=0;

    q.push(s);

    while(!q.empty())

    {

        int u=q.front();

        for(int l=0; l<graph[u].size(); l++)

        {

            int v = graph[u][l];

            if(!visited[v])

            {

                visited[v]=1;

                level[v] = level[u]+1;

                q.push(v);

            }

        }

        q.pop();

    }

   printf("%2d to %2d: %d\n", s, d, level[d]);

}

int main()

{

    int x, y, caseno=0;

    while(scanf("%d",&x)==1)

    {

        for(int j=0; j<x; j++)

        {

            scanf("%d",&y);

            graph[1].push_back(y);

            graph[y].push_back(1);

        }

        for(int i=2; i<=19; i++)

        {

            scanf("%d",&x);

            for(int j=0; j<x; j++)

            {

                scanf("%d",&y);

                graph[i].push_back(y);

                graph[y].push_back(i);

            }

        }

        int src, dest, n;

        scanf("%d",&n);

        printf("Test Set #%d\n",++caseno);

        for(int i=0; i<n; i++)

        {

            scanf("%d %d",&src, &dest);

            bfs(src,dest);

        }

       printf("\n");

       for(int i=0; i<21; i++)

       {

           graph[i].clear();

       }

    }

    return 0;

}

=> Need Help . Leave a Comment .