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, int &c0, int &c1) { 
  62.     queue <int> q;
  63.     q.push(s);
  64.     color[s] = 0;
  65.     c0++;
  66.     while (!q.empty()) {
  67.         int u = q.front();
  68.         q.pop();
  69.         for (int v : adj[u]) {
  70.             if(color[v] == color[u]){
  71.             	return false;
  72.             }
  73.             else if(color[v] == -1){
  74.             	color[v] = !color[u];
  75.             	q.push(v);
  76.             	if(color[v] == 1) c1++;
  77.             	else c0++;
  78.             }
  79.         }
  80.     }
  81.     return true;
  82. }
  83. int main() {
  84. 	//freopen("BFS.INP", "r", stdin);
  85. 	//freopen("BFS.OUT", "w", stdout);
  86. 	ios_base::sync_with_stdio(0);
  87. 	memset(color, -1, sizeof(color));
  88. 	bool ok = false;
  89. 	nhap();
  90. 	int ans = 0;
  91. 	for(int i = 1; i <= n ; i++){
  92. 		if(color[i] == -1){
  93. 			int c0 = 0, c1 = 0;
  94. 			if( bfs(i, c0, c1) ){
  95. 				ans += min(c0, c1);
  96.     	        ok = true;
  97.             }
  98.             else{
  99.             	cout << "Impossible" << nn;
  100.             	ok = false;
  101.             	return 0;
  102.             } 
  103. 		}
  104. 	}
  105. 	if(ok) cout << ans << nn;
  106.  
  107. }
Success #stdin #stdout 0.01s 6372KB
comments (?)
stdin
copy 
3 2
1 2
2 3
stdout
copy 
1
https://ideone.com/CfYw25
language:
C++14 (gcc 8.3)
created:
1 day 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!