fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5.  
  6.  
  7. const int M = 1000000007;
  8. const int N = 3e5+9;
  9. const int INF = 2e9+1;
  10. const int MAXN = 100000;
  11. const int LINF = 2000000000000000001;
  12.  
  13. //_ ***************************** START Below *******************************
  14.  
  15.  
  16. //* Child BFS : 
  17. //* 	Visited marked in child
  18. //* 	Each Node visited once only i.e. queue contains distinct
  19.  
  20. //*         1							
  21. //* 	 /  |  \								
  22. //*    2    5   6												
  23. //*    |    | /								
  24. //*    3 -- 4			
  25. //*  4's is 1st explored by 5 i.e. put in queue (visited)
  26. //* 		lvl[4] = 2
  27. //* 		dp[4] = dp[5] + 1
  28.  
  29. //*  4's 2nd visit => can't be explored by 6 (already visited) 
  30. //* 	But can be checked for shortest path 
  31. //*			lvl[6] + 1 == lvl[4] i.e. shortest path
  32. //* 		dp[4] = dp[6] + 1
  33.  
  34. //*  4's 3rd visit => can't be explored by 3 (already visited) 
  35. //* 	But can be checked for shortest path 
  36. //*			lvl[3] + 1 > lvl[4] i.e. not shortest path
  37.  
  38.  
  39.  
  40. vector<vector<int>> graph;
  41. void consistency(int n, int m){
  42.  
  43. 	vector<int> dp(n+1, 0);
  44.  
  45. 	queue<int> q;
  46. 	q.push(1);
  47. 	vector<int> visited(n+1, false);
  48. 	vector<int> levels(n+1, 0);
  49. 	dp[1] = 1;
  50. 	visited[1] = true;
  51.  
  52.  
  53. 	while(!q.empty()){
  54.  
  55. 		auto node = q.front(); q.pop();
  56.  
  57. 		for(int ch : graph[node]){
  58. 			if(ch == node) continue;
  59. 			if(visited[ch]){
  60. 				//* 2nd time visit (may not be via shortest path, need to check)
  61. 				//* Child is already visited and present in queue (to be explored)
  62. 				//* So we don't explore it (i.e. no q.push(ch) )
  63.  
  64. 				if(levels[node]+1 == levels[ch]){
  65. 					dp[ch] += dp[node];
  66. 				}
  67.  
  68. 			}
  69. 			else{
  70. 				//* 1st time visit => gurantees to be shortest (child bfs)
  71. 				q.push(ch);
  72. 				visited[ch] = true;
  73. 				levels[ch] = levels[node]+1;
  74. 				dp[ch] += dp[node];
  75. 			}
  76. 		}
  77.  
  78.  
  79. 	}
  80.  
  81. 	for(int i=1; i<=n; i++){
  82. 		cout << dp[i] << " ";
  83. 	}cout << endl;
  84.  
  85.  
  86. }
  87.  
  88.  
  89.  
  90. void solve() {
  91.  
  92. 	int n, m;
  93. 	cin >> n >> m;
  94.  
  95. 	graph.resize(n+1); // 1 based indexing
  96. 	for(int i=0; i<m; i++){
  97. 		int x, y;
  98. 		cin >> x >> y;
  99. 		graph[x].push_back(y);
  100. 		graph[y].push_back(x);
  101. 	}
  102.  
  103. 	consistency(n, m);
  104.  
  105.  
  106. }
  107.  
  108.  
  109.  
  110.  
  111.  
  112. int32_t main() {
  113.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  114.  
  115.     int t = 1;
  116.     while (t--) {
  117.         solve();
  118.     }
  119.  
  120.     return 0;
  121. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
4 4
1 2
1 3
2 4
3 4
stdout
copy 
1 1 1 2
https://ideone.com/iGddXB
language:
C++14 (gcc 8.3)
created:
2 days 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!