fork(3) download
copy 
  1. #include<stdio.h>
  2. #include<vector>
  3. using namespace std;
  4.  
  5. vector<int> graph[100019];
  6. int mvc[100019];
  7.  
  8. int mvc_tree(int v)
  9. {
  10. 	mvc[v] = -1;
  11. 	if(graph[v].size() == 1)
  12. 		return 0;
  13. 	int x = 0;
  14. 	for(int i = 0; i < graph[v].size(); ++i)
  15. 		if(!mvc[graph[v][i]])
  16. 		{
  17. 			x += mvc_tree(graph[v][i]);
  18. 			if(mvc[v] < 1 && mvc[graph[v][i]] < 1)
  19. 				++x,
  20. 				mvc[v] = 1;
  21. 		}
  22. 	return x;
  23. }
  24.  
  25. int main()
  26. {
  27. 	int t, n, a, b, i;
  28.  
  29. 	scanf("%d", &t);
  30. 	while(t--)
  31. 	{
  32. 		scanf("%d", &n);
  33. 		for(i = 1; i <= n; ++i)
  34. 			graph[i].clear();
  35. 		for(i = 1; i < n; ++i)
  36. 		{
  37. 			scanf("%d%d", &a, &b);
  38. 			graph[a].push_back(b);
  39. 			graph[b].push_back(a);
  40. 			mvc[i] = 0;
  41. 		}
  42. 		mvc[n] = 0;
  43. 		if(n < 3)
  44. 		{
  45. 			puts("1");
  46. 			continue;
  47. 		}
  48. 		for(i = 1; i <= n; ++i)
  49. 			if(graph[i].size() > 1)
  50. 				break;
  51. 		printf("%d\n", mvc_tree(i));
  52. 	}
  53. 	return 0;
  54. }
Success #stdin #stdout 0s 4380KB
comments (?)
stdin
copy 
2 
4 
1 2 
2 3 
3 4 
3 
1 2 
1 3
stdout
copy 
2
1
https://ideone.com/mV4bqg
language:
C++ 4.3.2 (gcc-4.3.2)
created:
12 years ago
visibility:
secret

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!