fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. #include<iterator>
  3. #include<vector>
  4. #include<queue>
  5. #include<map>
  6. #include<set>
  7. #include<string>
  8. #define pb push_back
  9. #define f first
  10. #define s second
  11. #define MX 100000
  12. using namespace std;
  13.  
  14. const int inf =10000;
  15. map<int,int>mp;
  16. map<int,int>::iterator it1;
  17. set<int>st;
  18. set<int>::iterator it;
  19. vector<int>adj[MX],cost[MX];
  20.  
  21. int cs=1;
  22. void bfs(int s,int d){
  23. 	int dis[MX],path[MX];
  24. 	queue<int>q;
  25. 	for(it=st.begin();it!=st.end();it++) mp[*it]=-1;
  26. 	dis[s]=0;mp[s]=1;
  27. 	q.push(s);
  28. 	while(!q.empty()){
  29. 		int u=q.front();
  30. 		q.pop();
  31. 		for(int i=0;i<adj[u].size();i++){
  32. 			int v=adj[u][i];
  33. 			dis[v]=dis[u]+1;
  34. 			if(mp[v]==-1 && dis[v]<d+1){
  35. 				mp[v]=1;
  36. 				q.push(v);
  37. 			}
  38. 		}
  39. 	}
  40. 	int yet=0;
  41. 	for(it1=mp.begin();it1!=mp.end();it1++) {
  42. 		if(((*it1).s)!=1) yet++;
  43. 	}
  44. 	printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",cs++,yet,s,d);
  45. }
  46. int main(){
  47. 	int e,n,x1,x2,w,s,d;
  48. 	while(scanf("%d",&e)==1 && e!=0){
  49. 		while(e--){
  50. 			scanf("%d%d",&x1,&x2);
  51. 			adj[x1].pb(x2);adj[x2].pb(x1);
  52. 			st.insert(x1);st.insert(x2);
  53. 		}
  54. 		while(scanf("%d%d",&s,&d)==2 && s!=0 && d!=0){
  55. 			bfs(s,d);
  56. 		}
  57. 		adj[MX].clear();st.clear();mp.clear();
  58. 	}
  59. 	return 0;
  60. }
Success #stdin #stdout 0s 20200KB
comments (?)
stdin
copy 
16
10 15 15 20 20 25 10 30 30 47 47 50 25 45 45 65
15 35 35 55 20 40 50 55 35 40 55 60 40 60 60 65
35 2 35 3 0 0
14
1 2 2 7 1 3 3 4 3 5 5 10 5 11
4 6 7 6 7 8 7 9 8 9 8 6 6 11
1 1 1 2 3 2 3 3 0 0
0
stdout
copy 
Case 1: 5 nodes not reachable from node 35 with TTL = 2.
Case 2: 1 nodes not reachable from node 35 with TTL = 3.
Case 3: 8 nodes not reachable from node 1 with TTL = 1.
Case 4: 5 nodes not reachable from node 1 with TTL = 2.
Case 5: 5 nodes not reachable from node 3 with TTL = 2.
Case 6: 3 nodes not reachable from node 3 with TTL = 3.
https://ideone.com/oAv35z
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!