fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <iostream>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <stack>
  7. #include <queue>
  8. #include <math.h>
  9. #include <string.h>
  10. #include <set>
  11. #include <map>
  12. #include <iostream>
  13. #include <sstream>
  14. #define MAXN 103
  15. #define ll long long int
  16. #define INF 0x3f3f3f3f
  17. #define PI acos(-1)
  18. #define MOD 1000000007LL
  19.  
  20. using namespace std;
  21.  
  22. int n, m, U, V, deg[MAXN], vis[MAXN];
  23. bool dp[MAXN][MAXN];
  24. bool can;
  25. vector<vector<int> > g(MAXN);
  26.  
  27. void dfs(int u, int father, int begin){
  28. 	if(can) return;
  29. 	vis[u] = 1;
  30. 	for(int i = 0; i < g[u].size(); i++){
  31. 		int next = g[u][i];
  32. 		if(next == begin && father != begin){
  33. 			can = 1;
  34. 			break;
  35. 		}else{
  36. 			if(!vis[next]){
  37. 				dfs(next, u, begin);
  38. 			}
  39. 		}
  40. 	}
  41. }
  42.  
  43. int main(){
  44. 	while(scanf("%d%d", &n, &m) && n > -1 && m > -1){
  45. 		memset(deg, 0, sizeof(deg));
  46. 		for(int i = 1; i <= n; i++){
  47. 			g[i].clear();
  48. 			vis[i] = 0;
  49. 		}
  50. 		for(int i = 0; i < m; i++){
  51. 			scanf("%d%d", &U, &V);
  52. 			g[U].push_back(V);
  53. 			g[V].push_back(U);
  54. 			deg[U]++;
  55. 			deg[V]++;
  56. 		}
  57. 		bool go = true;
  58. 		int ans = 0;
  59. 		while(go){
  60. 			go = false;
  61. 			int idxA = -1, idxB = -1;
  62. 			for(int j = 1; j <= n; j++){
  63. 				if(deg[j] < 2){
  64. 					idxA = j;
  65. 					break;
  66. 				}
  67. 			}
  68. 			for(int j = 1; j <= n; j++){
  69. 				if(deg[j] < 2 && idxA != j){
  70. 					idxB = j;
  71. 					break;
  72. 				}
  73. 			}
  74. 			if(idxA == -1 && idxB == -1){
  75. 				break;
  76. 			}
  77. 			if(idxA != -1){
  78. 				deg[idxA]++;
  79. 				go = 1;
  80. 			}
  81. 			if(idxB != -1){
  82. 				deg[idxB]++;
  83. 				go = 1;
  84. 			}else{
  85. 				if(idxA != -1){
  86. 					if(deg[idxA] < 2){
  87. 						deg[idxA]++;
  88. 					}
  89. 				}
  90. 			}
  91. 			ans++;
  92. 		}
  93. 		vector<int> candidate;
  94. 		if(ans == 0){
  95. 			for(int i = 1; i <= n; i++){
  96. 				memset(vis,0,sizeof(vis));
  97. 				if(!vis[i]){
  98. 					can = 0;
  99. 					dfs(i, -1, i);
  100. 					if(!can){
  101.  
  102. 						candidate.push_back(i);
  103. 					}
  104. 				}
  105. 			}
  106. 		}
  107. 		printf("%d\n", ans + ((int)candidate.size()+1) / 2 );
  108. 	}
  109. 	return 0;
  110. }
  111.  
Success #stdin #stdout 0s 2872KB
comments (?)
stdin
copy 
26 31
1 2
2 3
1 3
2 7
7 26
7 4
7 15
26 19
19 20
19 21
20 21
10 9
10 11
9 11
11 8
8 12
12 14
12 13
13 14
23 25
24 25
23 24
22 23
6 22
6 5
6 4
4 5
15 16
16 17
16 18
18 17

7 8
1 2
2 3
1 3
2 7
7 4
4 6
6 5
5 4


7 8
1 2
2 3
1 3
2 7
7 4
4 6
6 5
5 4

9 11
1 2
2 3
3 1
2 4
4 3
4 5
6 9
6 7
8 6
8 7
8 9

7 8
1 2
1 3
2 3
2 7
7 4
4 6
6 5
5 4

3 1
1 3

9 10
1 2
2 3
1 3
7 9
5 9
5 7
6 8
4 6
4 8
8 9

4 4
1 2
1 4
1 3
2 3

12 9
1 7
2 6
4 9
9 10
8 12
1 5
1 8
8 11
4 10

4 2
1 2
2 3

7 5
4 5
4 3
3 2
1 6
1 7

6 4
1 2
1 3
3 4
6 5

11 10
1 10
10 2
2 4
2 3
10 5
5 6
5 7
5 8
5 9
8 11

8 6
4 5
4 6
4 7
6 8
1 3
3 2

6 5
1 2
2 5
2 3
3 4
3 6

8 8
1 2
2 3
3 4
4 5
2 6
3 7
4 8
7 8

11 8
1 2
2 3
3 4
4 5
3 7
3 6
3 8
9 10

5 4
1 2
2 3
3 5
1 4

10 7
1 2
2 3
3 5
3 6
3 10
3 4
7 8

-1 -1
stdout
copy 
3
1
1
1
1
2
0
1
4
2
2
2
4
3
2
2
5
1
5
https://ideone.com/kMElYP
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 years 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!