fork download
copy 
  1. /*
  2. 	Amrutansu Garanaik
  3. 	This algorithm will only work for a tree (n-ary)
  4. */
  5.  
  6. #include <stdio.h>
  7. #include <vector>
  8. #include <algorithm>
  9. #include <list>
  10. #include <string.h>
  11. #define MAX 10000
  12.  
  13. using namespace std;
  14.  
  15.  
  16. vector <vector <int> > graph(MAX);
  17. int nodes;
  18. int edges;
  19. list <int> req_vertices;	//will store the vertices of minimum cover
  20.  
  21. int arr[MAX];			//vertex count
  22. int visit[MAX];
  23. //here tree is represented as a graph, not like we do in binary tree, so tree won't be empty
  24. int minimum_vertex_cover(int root)	//returns number of nodes
  25. {
  26. 	if(visit[root] == 1)
  27. 		return 0;
  28. 	if(graph[root].size() == 0)	//root has no child
  29. 		return 0;		//as this won't contribute to any edges
  30. 	if(arr[root] != -1)
  31. 		return arr[root];	//minimum vertex cover of subtree starting at root
  32.  
  33. 	int with_root = 1;
  34.  
  35. 	for(int i = 0; i < (int) graph[root].size(); i++)
  36. 	{
  37. 		if(visit[graph[root][i]] == 0)
  38. 			with_root += minimum_vertex_cover(graph[root][i]);
  39. 	}
  40.  
  41. 	int without_root = 0;
  42.  
  43. 	for(int i = 0; i < (int) graph[root].size(); i++)	//since this root is not included, its children are unvisited, so if their children are
  44. 							//visited, these nodes will be covered
  45. 	{
  46. 		int present = graph[root][i];
  47. 		for(int j = 0; j < (int) graph[present].size(); j++)
  48. 			if(visit[graph[present][i]] == 0)
  49. 				without_root += minimum_vertex_cover(graph[present][i]);
  50. 	}  
  51.  
  52. 	arr[root] = with_root < without_root ? with_root : without_root;
  53.  
  54. 	visit[root] = 1;
  55. 	return arr[root];
  56.  
  57. }
  58.  
  59. int main()
  60. {
  61. 	int a, b;
  62. 	printf("Enter number of nodes : ");
  63. 	scanf("%d", &nodes);
  64.  
  65. 	memset(arr, -1, sizeof(arr));
  66. 	memset(visit,  0, sizeof(visit));
  67.  
  68. 	printf("Enter number of edges : ");
  69. 	scanf("%d", &edges);
  70. 	printf("Enter the edges : ");
  71. 	for(int i=0; i<edges; i++)
  72. 	{
  73. 		scanf("%d%d",&a,&b);
  74. 		graph[a].push_back(b);
  75. 		graph[b].push_back(a);
  76. 	}
  77.  
  78. 	printf("Number of nodes in vertex cover : %d\n",minimum_vertex_cover(0));
  79.  
  80.  
  81.  
  82. 	return 0;
  83. }
Success #stdin #stdout 0s 2952KB
comments (?)
stdin
copy 
8 7
0 1
1 2
1 3
3 4
3 5
0 6
6 7
stdout
copy 
Enter number of nodes : Enter number of edges : Enter the edges : Number of nodes in vertex cover : 0
https://ideone.com/IppUMI
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!