Thursday, 18 February 2016

UVa 336 - A Node Too Far

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int edges,cas=1;
    while(cin>>edges)
    {
        if(edges==0)
            break;
        vector<long long int>nodes[100000];
        map<long long ,int>difference;
        difference.clear();
        int i,j,a,b,num=0;
        for(i=0;i<edges;i++)
        {
            cin>>a>>b;
            nodes[a].push_back(b);
            nodes[b].push_back(a);
            if(difference[a]!=1)
            {
                difference[a]=1;
                num++;
            }
            if(difference[b]!=1)
            {
                difference[b]=1;
                num++;
            }
        }
        map<long long ,int>visited;
        map<long long ,int>level;
        visited.clear();
        level.clear();
        int start,ttl;
        int number;
        queue<long long int>q;
        //int c=0;
        while(cin>>start>>ttl)
        {
            if(start==0 && ttl==0)
                break;
            number=0;
            visited.clear();
            visited[start]=1;
            level[start]=0;
            q.push(start);
            while(!q.empty())
            {
                int front=q.front();
                q.pop();
                int l=nodes[front].size();
                for(i=0;i<l;i++)
                {
                    if(visited[nodes[front][i]]!=1)
                    {
                        level[nodes[front][i]]=level[front]+1;
                        if(level[nodes[front][i]]>ttl)
                        {
                            break;
                        }
                        number++;
                        visited[nodes[front][i]]=1;
                        q.push(nodes[front][i]);
                    }
                }
                //q.pop();
            }
            printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",cas,num-number-1,start,ttl);
            cas++;
        }
    }
    return 0;

}

No comments:

Post a Comment