UvaSolution/336_A_Node_Too_Far.cpp at master · Masum95/UvaSolution · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
#define bug cout<<"bug";
#define pb(n) push_back(n)
#define lli long long int
#define fr(i,s,l) for(i=s;i<l;i++)
#define sf(n) scanf("%d",&n);

using namespace std;

int main()
{
    int kase=1;
    while(1)
    {
        int num;
        sf(num);
        if(num==0) return 0;

        vector<int> nodes[40];
        map<int,int> imap;
        int assin=0,ind=0;
        int level[40];
        for(int i=0; i<num; i++)
        {
            int f,s;
            int in1,in2;
            cin>>f>>s;  //array compression
            if(imap.find(f)==imap.end())
            {
                imap[f]=assin++;
            }
            in1=imap[f];
            if(imap.find(s)==imap.end())
            {
                imap[s]=assin++;
            }

            in2=imap[s];
            if(in1!=in2)
            {
                nodes[in1].push_back(in2);
                nodes[in2].pb(in1);
            }
            else
                nodes[in1].push_back(in2);

        }
        int st,ttl;

        while(1)
        {
            cin>>st>>ttl;
            int ans=0;
            if(st==0 && ttl==0)
            {
                break;
            }
            level[imap[st]]=0;
            queue<int> show;
            int vis[40]= {};
            show.push(imap[st]);
            vis[imap[st]]=1;

            while(!show.empty())
            {
                int top=show.front();

                show.pop();
                for(int i=0; i<nodes[top].size(); i++)
                {

                    int tmp=nodes[top][i];
                    if(!vis[tmp])
                    {
                        show.push(tmp);
                        vis[tmp]=1;
                        level[tmp]=level[top]+1;

                        if(level[tmp]<=ttl)
                            ans++;
                    }

                }
            }
            int total_node=assin-1;
   // cout<<total_node;
            printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",kase++,total_node-ans,st,ttl);


        }
    }


}