Saturday 5 May 2012

UVa 336 A Node Too Far Solution

#include<iostream>
#include<vector>
#include<map>
#include<queue>
using namespace std;
int main()
{
    long long nc,i,pair1,pair2,node,ttl,number,l,x,diff,cs=1;
    vector<long long>v[100000];
    map<long long,int>mp;
    map<long long,int>visit;
    map<long long,int>dif;
    queue<long long>q;
    while(cin>>nc)
    {
        if(nc==0)   return 0;
        diff=0;
        dif.clear();
        for(i=0;i<99900;i++)
        v[i].clear();
        mp.clear();
        for(i=0;i<nc;i++)
        {
            cin>>pair1>>pair2;
            v[pair1].push_back(pair2);
            v[pair2].push_back(pair1);
            if(dif[pair1]!=1)
            {
                dif[pair1]=1;
                diff++;
            }
            if(dif[pair2]!=1)
            {
                dif[pair2]=1;
                diff++;
            }
        }
        //cout<<diff<<endl;
        while(cin>>node>>ttl)
        {
            if(node==0 && ttl==0)
            break;
            number=0;
            visit.clear();
            visit[node]=1;
            mp[node]=0;
            q.push(node);
            while(!q.empty())
            {
                x=q.front();
                q.pop();
                l=v[x].size();
                for(i=0;i<l;i++)
                {
                    if(visit[v[x][i]]!=1)
                    {
                        mp[v[x][i]]=mp[x]+1;
                        if(mp[v[x][i]]>ttl)
                        break;
                        number++;
                        visit[v[x][i]]=1;
                        q.push(v[x][i]);
                    }
                }
            }

        cout<<"Case "<<cs<<": "<<diff-number-1<<" "<<"nodes not reachable from node "<<node<<" with TTL = "<<ttl<<"."<<endl;
        cs++;
        }
    }
}

No comments:

Post a Comment