UVa - 336 ( A Node Too Far Solution )

Try Yourself First. For help Scroll Down .

Tip : This is Basic BFS ( Breadth First Search ) problem . To solve this problem you need to have some idea about STL ( Queue at Standard Template Library ) and you have to learn Basic BFS simulation .. You can learn BFS from your Data Structures book, Topcoder Tutorial and from Much more online sites . For Bangladeshis I would like to mention a tutorial about Breadth First Search . First learn BFS and then solve this problem . For any Query you can Post a Comment here. I will try my best to answer your Query . Move on to the code .

Code :


#include<bits/stdc++.h>

using namespace std;
map< int, int > visited;

void BFS(int s, map< int, vector< int > >G)
{
    queue< int >q;
    q.push(s);
    visited[s] = 0;
    while(!q.empty())
    {
        int top = q.front();
        for(int i=0; i<G[top].size(); i++)
        {
           int n = G[top][i];
           if(!visited.count(n))
           {
               visited[n] = visited[top] + 1;
               q.push(n);
           }
        }
        q.pop();
    }
}



int main()
{
    int edges, cases=0;
    while(scanf("%d",&edges)==1 & edges!=0)
    {
        map< int,vector< int > >G;
        for(int i=0; i<edges; i++)
        {
            int x, y;
            scanf("%d %d", &x, &y);
            G[x].push_back(y);
            G[y].push_back(x);
        }
        int ttl, source;
        while(scanf("%d %d", &source, &ttl)==2)
        {
            if(source==0 && ttl==0) break;
            map< int, int>::iterator it;
            visited.clear();
            BFS(source,G);
            int count=0;
            for(it=visited.begin(); it!=visited.end();++it)
            {
                //cout<<(*it).first<<' '<<(*it).second<<endl;
                if((*it).second>ttl){
                    ++count;
                }
            }
            //cout<<G.size()<<' '<<visited.size()<<endl;
            count = count + G.size()-visited.size();
            printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",++cases,count, source, ttl);
        }
    }
    return 0;
}

=> Need help . Leave a Comment .