#include <bits/stdc++.h>
#define sf scanf
#define pf printf
using namespace std;
map<int, int>visited;
void bfs(int start, map<int, vector<int> > graph)
{
queue<int>q;
q.push(start);
visited[start] = 0;
while(!q.empty()){
int top = q.front();
q.pop();
int size = graph[top].size();
for(int i=0; i<size; i++){
int n = graph[top][i];
if(!visited.count(n)){
visited[n]=visited[top]+1;
q.push(n);
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
int nodes , a , b , kase =0;
while(cin >> nodes && nodes){
map<int, vector<int> >graph;
for(int i=0; i<nodes; i++){
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
int ttl , start;
while(cin >> start >> ttl ){
if(start==0 && ttl ==0)break;
map<int, int>::const_iterator it;
visited.clear();
bfs(start , graph);
int cnt =0;
for(it = visited.begin(); it!=visited.end(); it++){
if((*it).second >ttl)cnt++;
}
cnt += graph.size()-visited.size();
cout << "Case "<<++kase << ": "<<cnt <<" nodes not reachable from node "<<start<<" with TTL = "<<ttl<<".\n";
}
}
}
#define sf scanf
#define pf printf
using namespace std;
map<int, int>visited;
void bfs(int start, map<int, vector<int> > graph)
{
queue<int>q;
q.push(start);
visited[start] = 0;
while(!q.empty()){
int top = q.front();
q.pop();
int size = graph[top].size();
for(int i=0; i<size; i++){
int n = graph[top][i];
if(!visited.count(n)){
visited[n]=visited[top]+1;
q.push(n);
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
int nodes , a , b , kase =0;
while(cin >> nodes && nodes){
map<int, vector<int> >graph;
for(int i=0; i<nodes; i++){
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
int ttl , start;
while(cin >> start >> ttl ){
if(start==0 && ttl ==0)break;
map<int, int>::const_iterator it;
visited.clear();
bfs(start , graph);
int cnt =0;
for(it = visited.begin(); it!=visited.end(); it++){
if((*it).second >ttl)cnt++;
}
cnt += graph.size()-visited.size();
cout << "Case "<<++kase << ": "<<cnt <<" nodes not reachable from node "<<start<<" with TTL = "<<ttl<<".\n";
}
}
}
No comments:
Post a Comment