Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define fora(i,n) for(int i=0 ; i<n ; i++)
- #define pb(x) push_back(x)
- using namespace std;
- unordered_map <int, vector <int> > adj;
- //vector <int> level(35),vis(35);
- int level[35],vis[35];
- int cs;
- int bfs(int src,int ttl) {
- int ans=0;
- vis[src]=1;
- level[src]=0;
- queue <int> q;
- q.push(src);
- while(!q.empty()) {
- int u=q.front();q.pop();
- //unordered_map <int, vector <int> > :: iterator &v;
- for(auto v : adj[u]) {
- if(vis[v]==0) {
- //nd++;
- vis[v]=1;
- level[v]=level[u]+1;
- //cout << (v) << ": " << level[v] << endl;
- if(level[v]>ttl) ans++;
- q.push(v);
- }
- }
- }
- return ans;
- }
- int main() {
- cs=1;
- while(1) {
- int e;
- cin >> e;
- if(e==0) break;
- fora(i,e) {
- int x,y;
- cin >> x >> y;
- adj[x].pb(y);
- adj[y].pb(x);
- }
- for( ; ; cs++) {
- int src,ttl;
- cin >> src >> ttl;
- memset(vis,0,sizeof vis);
- memset(level,-1,sizeof level);
- if(src==0 && ttl==0) {
- cs--;
- break;
- }
- int ans=bfs(src,ttl);
- //cout << bfs(src,ttl) << endl;
- printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",cs,ans,src,ttl);
- }
- adj.clear();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement