Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long int
- #define pb push_back
- #define initial(arr,N) memset(arr,N,sizeof(arr))
- vector<ll> Vector[300];
- queue<ll> Queue;
- map<ll, ll> Map;
- ll assigned ;
- void Input(ll NC);
- ll BFS(ll SourceNode,ll TTL);
- void Input(ll NC)
- {
- ll i, j;
- assigned = 0 ;
- for (i = 0; i < NC; i++)
- {
- ll First, Second ;
- cin >> First>> Second;
- if (Map.find(First) == Map.end())
- {
- Map[First] = assigned;
- assigned++;
- }
- if (Map.find(Second) == Map.end())
- {
- Map[Second] = assigned;
- assigned++;
- }
- Vector[Map[First]].pb(Map[Second]);
- Vector[Map[Second]].pb(Map[First]);
- }
- return;
- }
- ll BFS(ll SourceNode,ll TTL)
- {
- ll i, j , Source;
- ll Visited[300] = {};
- ll Level[300] ;
- initial(Level,-1);
- Source = Map[SourceNode];
- Queue.push(Source);
- Level[Source] = 0;
- Visited[Source] = 1 ;
- while (!Queue.empty())
- {
- ll Node;
- Node = Queue.front();
- Queue.pop();
- for (i = 0; i < Vector[Node].size(); i++)
- {
- if (Visited[Vector[Node][i]]==0)
- {
- Visited[Vector[Node][i]] = 1;
- Level[Vector[Node][i]] = Level[Node] + 1 ;
- Queue.push(Vector[Node][i]);
- }
- }
- }
- ll counter = 0;
- for (i = 0; i < assigned; i++)
- {
- if (Level[i]>=0 && Level[i]<=TTL)
- {
- counter++;
- }
- }
- return assigned - counter;
- }
- int main()
- {
- //freopen("in.txt","r",stdin);
- ll NC, Unreached , SourceNode , TTL, t=0;
- while ((cin >> NC) && NC)
- {
- Input(NC);
- while ((cin >> SourceNode >> TTL) && (SourceNode || TTL))
- {
- t++;
- Unreached = BFS(SourceNode, TTL);
- printf("Case %lld: %lld nodes not reachable from node %lld with TTL = %lld.\n", t, Unreached, SourceNode, TTL);
- }
- for(int i=0 ; i<300 ; i++)
- {
- Vector[i].clear();
- }
- Map.clear();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement