fork(1) download
copy 
  1.  
  2. #include <stdio.h>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <list>
  6. #include <string.h>
  7. #define MAX 10000
  8.  
  9. using namespace std;
  10.  
  11.  
  12. vector <vector <int> > graph(MAX);
  13. int nodes;
  14. int edges;
  15. list <int> req_vertices;	//will store the vertices of minimum cover
  16.  
  17. int arr[MAX];			//vertex count
  18.  
  19. //here tree is represented as a graph 
  20. int minimum_vertex_cover(int root)	//returns number of nodes
  21. {
  22. 	if(graph[root].size() == 0)	
  23. 		return 0;	
  24. 	if(arr[root] != -1)
  25. 		return arr[root];	
  26.  
  27. 	int with_root = 1;
  28.  
  29. 	for(int i = 0; i < (int) graph[root].size(); i++)
  30. 		with_root += minimum_vertex_cover(graph[root][i]);
  31.  
  32. 	int without_root = graph[root].size();
  33.  
  34. 	for(int i = 0; i < (int) graph[root].size(); i++)	
  35. 	{
  36. 		int present = graph[root][i];
  37. 		for(int j = 0; j < (int) graph[present].size(); j++)
  38. 			without_root += minimum_vertex_cover(graph[present][j]);
  39. 	}  
  40.  
  41. 	arr[root] = with_root < without_root ? with_root : without_root;
  42.  
  43. 	return arr[root];
  44.  
  45. }
  46.  
  47. int main()
  48. {
  49. 	int a, b;
  50. 	printf("Enter number of nodes : ");
  51. 	scanf("%d", &nodes);
  52.  
  53. 	memset(arr, -1, sizeof(arr));
  54.  
  55. 	printf("Enter number of edges : ");
  56. 	scanf("%d", &edges);
  57. 	printf("Enter the edges : ");
  58. 	for(int i=0; i<edges; i++)
  59. 	{
  60. 		scanf("%d%d",&a,&b);
  61. 		graph[a].push_back(b);
  62. 		//graph[b].push_back(a);
  63. 	}
  64.  
  65. 	printf("Number of nodes in vertex cover : %d\n",minimum_vertex_cover(0));
  66.  
  67.  
  68.  
  69. 	return 0;
  70. }
Success #stdin #stdout 0s 2912KB
comments (?)
stdin
copy 
11 10
0 1
0 2
0 3
2 4
2 5
4 9
4 10
3 6
3 7
3 8
stdout
copy 
Enter number of nodes : Enter number of edges : Enter the edges : Number of nodes in vertex cover : 4
https://ideone.com/7jk1DT
language:
C++ 4.3.2 (gcc-4.3.2)
created:
7 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!