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. //* Parent BFS : 
  17. //* 	Not suited : TLE / MLE
  18. //* 	Visited marked in parent
  19. //* 	Node might be visited twice i.e. queue contains duplicates
  20.  
  21. //*         1							
  22. //* 	 /    \									
  23. //*    2        5														
  24. //*    |        | 									
  25. //*    3 ------ 4			
  26. //*  4 is 1st explored by 5 and put in queue (not visited yet)
  27. //* 		lvl[4] = 2
  28.  
  29. //*  4 is again explored by 3 and put in queue (not visited yet)
  30. //* 		lvl[4] = 3 ❌
  31. //* 		lvl[4] = min(lvl[4), lvl[3]+1 ) = 2
  32.  
  33.  
  34.  
  35. vector<vector<int>> graph;
  36. void consistency(int n, int m){
  37.  
  38. 	queue<int> q;
  39. 	q.push(1);
  40. 	vector<int> visited(n+1, false);
  41. 	vector<int> levels(n+1, INF);
  42. 	levels[1] = 0;
  43.  
  44. 	while(!q.empty()){
  45. 		auto node = q.front(); q.pop();
  46.  
  47. 		if(visited[node]) continue;
  48. 		visited[node] = true;
  49.  
  50. 		for(int ch : graph[node]){
  51. 			if(visited[ch]) continue;
  52.  
  53. 			q.push(ch);
  54. 			levels[ch] = min(levels[ch], levels[node]+1);
  55. 		}
  56.  
  57. 	}
  58.  
  59. 	for(int i=1; i<=n; i++){
  60. 		cout << levels[i] << " ";
  61. 	}cout << endl;
  62.  
  63.  
  64. }
  65.  
  66.  
  67.  
  68. void solve() {
  69.  
  70. 	int n, m;
  71. 	cin >> n >> m;
  72.  
  73. 	graph.resize(n+1); // 1 based indexing
  74. 	for(int i=0; i<m; i++){
  75. 		int x, y;
  76. 		cin >> x >> y;
  77. 		graph[x].push_back(y);
  78. 		graph[y].push_back(x);
  79. 	}
  80.  
  81. 	consistency(n, m);
  82.  
  83.  
  84. }
  85.  
  86.  
  87.  
  88.  
  89.  
  90. int32_t main() {
  91.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  92.  
  93.     int t = 1;
  94.     while (t--) {
  95.         solve();
  96.     }
  97.  
  98.     return 0;
  99. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
5 5
1 2
1 5
2 3
5 4
stdout
copy 
0 1 2 2 1
https://ideone.com/JRnS1i
language:
C++14 (gcc 8.3)
created:
10 hours 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!