UVA-336 ( A NODE TO FAR ) ( Category : Bfs with Array Compression)

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=272

Solution:

#include<bits/stdc++.h>

using namespace std;

map<long long int,long long int>mp;

long long int visited[32];
vector<long long int>v[32];

long long int bfs(long long int s,long long int t,long long int node)
{
    memset(visited,-1,sizeof(visited));

    queue<long long int>q;

    visited[s]=0;
    q.push(s);

    long long int u,p;

    while(!q.empty())
    {
        u=q.front();
        q.pop();

        for(long long int i=0; i<v[u].size(); i++)
        {
            p=v[u][i];

            if(visited[p]==-1)
            {
                visited[p]=visited[u]+1;
                q.push(p);
            }

        }
    }
    long long int cnt=0;
    for(long long int i=1; i<node; i++)
    {
        if(visited[i]>t||visited[i]==-1) cnt++;
    }
    return cnt;
}

int main()
{

    long long int r,i,a,b,c,d,e,f,p=1;

    while(1)
    {
        cin>>r;
        if(r==0) break;

        c=1;

        for(i=0; i<r; i++)
        {
            cin>>a>>b;

            if(mp.find(a)==mp.end())
            {
                mp[a]=c;
                c++;
            }
            if(mp.find(b)==mp.end())
            {
                mp[b]=c;
                c++;
            }
            v[mp[a]].push_back(mp[b]);
            v[mp[b]].push_back(mp[a]);

        }

        while(1)
        {
            cin>>d>>e;
            if(d==0&&e==0) break;
            f=bfs(mp[d],e,c);
            cout<<"Case "<<p<<": "<<f<<" nodes not reachable from node "<<d<<" with TTL = "<<e<<"."<<endl;
            p++;

        }
        mp.clear();

        for(long long int w=0; w<32; w++) v[w].clear();
    }


}