Maruf_Hasan

336 A node too far

Dec 12th, 2018
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.12 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define M 100000
  4. //pair<int, int>p;
  5.  
  6.  
  7. int bfs(int dist [M],vector<int>adj[M],int s,int d,vector<int>ve)
  8. {
  9. //vector<int>ve;
  10. bool visited[M];
  11. set<int>st;
  12. for(int i=0;i<M;i++)
  13. dist[i]=M;
  14.  
  15. memset(visited,false,sizeof visited);
  16. queue<int>q;
  17. q.push(s);
  18. visited[s]=true;
  19. dist[s]=0;
  20. // ve.push_back(s);
  21. st.insert(s);
  22.  
  23. while(!q.empty())
  24. {
  25. int u=q.front();
  26. q.pop();
  27. //cout<<u<<" ";
  28. for(int i=0;i<adj[u].size();i++)
  29. {
  30. int v=adj[u][i];
  31. if(visited[v]==false)
  32. {
  33. //cout<<v<<endl;
  34. q.push(v);
  35. //ve.push_back(v);
  36. st.insert(v);
  37. visited[v]=true;
  38. dist[v]=dist[u]+1;
  39. }
  40. }
  41. }
  42.  
  43.  
  44.  
  45.  
  46. int cnt=0;
  47. //cout<<dist[ve[ve.size()-1]]<<endl;
  48.  
  49. for(int i=0;i<ve.size();i++)
  50. {
  51. if(dist[ve[i]]<=d)
  52. cnt++;
  53. }
  54. return ve.size()-cnt;
  55. }
  56.  
  57.  
  58. int main()
  59. {
  60. int n,i,c=1;
  61. while(scanf("%d",&n)==1)
  62. {
  63.  
  64.  
  65.  
  66. int dist[M];
  67. if(n==0)break;
  68. vector<int>adj[M];
  69. vector<int>ve;
  70. //
  71. set<int>st;
  72. int x,y,rem,count=0,source,dis;
  73. for(i=0;i<n;i++)
  74. {
  75. cin>>x>>y;
  76. if(x==0 && y==0)
  77. break;
  78. else
  79. {
  80. adj[x].push_back(y);
  81. adj[y].push_back(x);
  82. st.insert(x);
  83. st.insert(y);
  84.  
  85. //count++;
  86. }
  87. }
  88.  
  89. set<int> :: iterator it;
  90. for(it=st.begin();it!=st.end();it++)
  91. {
  92. ve.push_back(*it);
  93. }
  94.  
  95. while(scanf("%d %d",&source,&dis)==2)
  96. {
  97. if(source==0 && dis==0)
  98. break;
  99. int ans;
  100. ans=bfs(dist,adj,source,dis,ve);
  101. printf("Case %d: %d nodes not reachable from node %d with TTL = %d\n",c++,ans,source,dis);
  102. }
  103. }
  104.  
  105. return 0;
  106. }
Advertisement
Add Comment
Please, Sign In to add comment