Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <queue>
- #include <set>
- using namespace std;
- int main()
- {
- long long NC, i, j, k, u, v, nodes, maxi, reach, kase = 1, ttl, lev;
- vector<long long> graph[100100];
- set<long long> s;
- while((scanf("%lld", &NC) == 1) && NC){
- maxi = 0;
- for(i = 0; i < NC; i++){
- scanf("%lld %lld", &u, &v);
- graph[u].push_back(v);
- graph[v].push_back(u);
- if(maxi < max(u, v))maxi = max(u, v);
- s.insert(u);
- s.insert(v);
- //printf("%d\n", s.size());
- }
- nodes = s.size();
- while(scanf("%lld %lld", &u, &v) == 2){
- if(u == 0 && v == 0)break;
- ttl = v;
- queue<int>Q[35];
- lev = 0;
- Q[lev].push(u);
- int visited[100100] = {0};
- visited[u] = 1;
- reach = 1;
- while(ttl){
- while(!Q[lev].empty()){
- k = Q[lev].front();
- Q[lev].pop();
- int si = graph[k].size();
- for(i = 0; i < si; i++){
- j = graph[k][i];
- if(visited[j] == 0){
- reach++;
- visited[j] = 1;
- Q[lev+1].push(j);
- }
- }
- }
- lev++;
- ttl--;
- }
- printf("Case %lld: %lld nodes not reachable from node %lld with TTL = %lld.\n", kase++, nodes-reach, u, v);
- for(i = 0; i <= lev; i++){
- while(!Q[i].empty())Q[i].pop();
- }
- }
- s.erase(s.begin(), s.end());
- for(i = 0; i <= maxi; i++){
- graph[i].erase(graph[i].begin(), graph[i].end());
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement