fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define ul unsigned long long
  6. #define nn "\n"
  7.  
  8. ll mod = 1e9+7;
  9. const int N = 1e5 + 5;
  10. int MOD = 998244353;
  11. int bit[200000];
  12. int n, m;
  13. vector<int> adj[N];
  14. int color[N];
  15.  
  16. void nhap(){
  17. 	cin >> n >> m ;
  18. 	int x,y;
  19. 	for(int i= 0 ; i < m ;  i++){
  20. 		cin >> x >> y;
  21. 		adj[x].push_back(y);
  22. 		adj[y].push_back(x);
  23. 	}
  24. }
  25. // void nhap(){
  26. // 	cin >> n >> m;
  27. // 	for(int i= 1 ; i <= n ;  i++){
  28. // 		for(int j= 1; j <= m ; j++){
  29. // 			cin >> a[i][j];
  30.  
  31. // 		}
  32. // 	}
  33. // }
  34. // void bfs(int sx, int sy) { 
  35. //     dem++;
  36. //     queue < pair <int, int> > q;
  37. //     q.push({sx, sy});
  38. //     visited[sx][sy] = true;
  39. //     while (!q.empty()) {
  40. //         int x = q.front().first;
  41. //         int y = q.front().second;
  42. //         q.pop();
  43.  
  44.  
  45. //         for (int i = 0; i < 4; ++i) {
  46. //             int u = x + sX[i];
  47. //             int v = y + sY[i];
  48.  
  49. //             if (u > n || u < 1) continue;
  50. //             if (v > m || v < 1) continue;
  51.  
  52.  
  53. //             if (a[u][v] != '#' && !visited[u][v]) {
  54. //                 visited[u][v] = true;
  55. //                 q.push({u, v});
  56. //             }
  57. //         }
  58.  
  59. //     }
  60. // }
  61. bool bfs(int s) { 
  62.     queue <int> q;
  63.     q.push(s);
  64.     color[s] = 0;
  65.     while (!q.empty()) {
  66.         int u = q.front();
  67.         q.pop();
  68.         for (int v : adj[u]) {
  69.             if(color[v] == color[u]){
  70.             	return false;
  71.             }
  72.             else if(color[v] == -1){
  73.             	color[v] = !color[u];
  74.             	q.push(v);
  75.             }
  76.         }
  77.     }
  78.     return true;
  79. }
  80. int main() {
  81. 	//freopen("BFS.INP", "r", stdin);
  82. 	//freopen("BFS.OUT", "w", stdout);
  83. 	ios_base::sync_with_stdio(0);
  84. 	memset(color, -1, sizeof(color));
  85. 	bool ok = false;
  86. 	nhap();
  87. 	for(int i = 1; i <= n ; i++){
  88. 		if(color[i] == -1){
  89. 			if( bfs(i) ){
  90.     	        ok = true;
  91.             }
  92.             else{
  93.             	cout << "IMPOSSIBLE" << nn;
  94.             	ok = false;
  95.             	return 0;
  96.             } 
  97. 		}
  98. 	}
  99. 	if(ok){
  100. 		for(int i = 1 ; i <= n; i++){
  101. 			cout << color[i] + 1 << " ";
  102. 		}
  103. 	}
  104.  
  105. }
Success #stdin #stdout 0.01s 6552KB
comments (?)
stdin
copy 
5 3
1 2
1 3
4 5
stdout
copy 
1 2 2 1 2
https://ideone.com/GK4nF0
language:
C++14 (gcc 8.3)
created:
5 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!