fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define maxsize 100100
  4. int n;
  5. vector<int> edges[maxsize];
  6. vector<int> vertex_cover(maxsize, 0);
  7. vector<int> visited(maxsize, 0);
  8.  
  9. void dfs(int current, int prev)
  10. {
  11. 	visited[current] = 1;
  12. 	// leaf node, add its parent to vertex cover
  13. 	if(edges[current].size() == 1 and edges[current][0] == prev)
  14. 	{
  15. 		vertex_cover[prev] = 1;
  16. 		return;
  17. 	}
  18. 	// internal node
  19. 	for(auto u: edges[current])
  20. 	{
  21. 		if(!visited[u])
  22. 			dfs(u, current);
  23. 	}
  24. 	// check if any of the children are marked already
  25. 	int flag = 0;
  26. 	for(auto u: edges[current])
  27. 	{
  28. 		if(u != prev and vertex_cover[u] == 1)
  29. 			flag = 1;
  30. 	}
  31. 	// none of its children are marked, mark the current node
  32. 	if(flag == 0)
  33. 		vertex_cover[current] = 1;
  34. }
  35. int main() {
  36. 	// Fast I/O
  37. 	ios_base::sync_with_stdio(false);
  38.     cin.tie(NULL);
  39.  
  40.     int i, u, v;
  41.     cin>>n;
  42.     for(i=1;i<n;i++)
  43.     {
  44.     	cin>>u>>v;
  45.     	edges[u].push_back(v);
  46.     	edges[v].push_back(u);
  47.     }	
  48.     dfs(1, 0);
  49.     int count = 0;
  50.     for(i=1;i<=n;++i)
  51.     {
  52.     	if(vertex_cover[i] == 1)
  53.     		count++;
  54.     	// cout<<i<<" "<<vertex_cover[i]<<"\n";
  55.     }
  56.     cout<<count<<"\n";
  57. 	return 0;
  58. }
Success #stdin #stdout 0s 6200KB
comments (?)
stdin
copy 
9
1 2
2 4
1 3 
3 5 
5 7
7 9
3 6
6 8
stdout
copy 
3
https://ideone.com/Z3VD2L
PT07X - Vertex Cover
language:
C++14 (gcc 8.3)
created:
3 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!