মঙ্গলবার, ৩১ জানুয়ারী, ২০১৭

UVA 336 - A Node Too Far

#include<bits/stdc++.h>
#include<string>
using namespace std;
vector<long long >vec[100000];
map<long long,long long>vis,visit,dist;
queue<long long>q;
main()
{
    long long n,cs=1,i;
    while(cin>>n)
    {
        if(n==0)
            break;
            dist.clear();
            vis.clear(),visit.clear();
            for(i=0;i<=100000;i++)
            {
                vec[i].clear();
            }
        long long a,b,no=0;

        for(i=1;i<=n;i++)
        {
            cin>>a>>b;
            vec[a].push_back(b);
            vec[b].push_back(a);
            if(vis[a]==0)
            {
                vis[a]=1;
                no++;
            }
            if(vis[b]==0)
            {
                vis[b]=1;
                no++;
            }
        }
        long long x,y,no1=0,x1,y1;
        while(cin>>x>>y)
        {
            no1=0;
            if(x==0&&y==0)
                break;
                visit.clear();
            q.push(x);
            visit[x]=1;
            dist[x]=0;
            while(!q.empty())
            {
                x1=q.front();
                q.pop();
                y1=vec[x1].size();
                for(i=0;i<y1;i++)
                {
                    if(visit[vec[x1][i]]==0)
                    {
                        dist[vec[x1][i]]=dist[x1]+1;
                        if(dist[vec[x1][i]]>y)
                            break;
                        no1++;
                        visit[vec[x1][i]]=1;
                        q.push(vec[x1][i]);
                    }
                }
            }
            printf("Case %lld: %lld nodes not reachable from node %lld with TTL = %lld.\n",cs++,no-no1-1,x,y);
        }
    }
}

কোন মন্তব্য নেই:

একটি মন্তব্য পোস্ট করুন

Factorization with prime Sieve

vector <int> prime; char sieve[1000009]; int N=1000009; void primeSieve ( ) { sieve[0] = sieve[1] = 1; prime.push_back(2); ...