fork download
copy 
  1. /*
  2. 	Amrutansu Garanaik
  3. 	Will work on tree only
  4. 	tree is represented using stucture
  5. */
  6.  
  7. #include <stdio.h>
  8. #include <list>
  9. #include <vector>
  10. #include <string.h>
  11. #include <stdlib.h>
  12. #define MAX 10000
  13.  
  14. using namespace std;
  15.  
  16. struct tree
  17. {
  18. 	int min_vertex;
  19. 	vector <struct tree *> child;
  20. };
  21.  
  22. int vertex_cover(struct tree *root)
  23. {
  24. 	if(root == NULL)
  25. 		return 0;
  26. 	if((root->child).size() == 0)	//no children
  27. 		return 0;
  28. 	if(root->min_vertex != -1)
  29. 		return root->min_vertex;
  30.  
  31.  
  32. 	int with_root = 1;
  33. 	for(int i = 0; i < (root->child).size(); i++)
  34. 		with_root += vertex_cover(root->child[i]);
  35.  
  36. 	int without_root = (root->child).size();
  37.  
  38. 	for(int i = 0; i < (root->child).size(); i++)
  39. 	{
  40. 		for(int j = 0; j < (root->child[i]->child).size(); j++)
  41. 			without_root += vertex_cover((root->child[i]->child)[j]);
  42. 	}
  43.  
  44. 	root->min_vertex = with_root < without_root ? with_root : without_root;
  45. 	return root->min_vertex;
  46. }
  47. struct tree * newNode()
  48. {
  49. 	struct tree *temp = (struct tree *) malloc(sizeof(struct tree));
  50. 	temp->min_vertex = -1;
  51. 	temp->child.clear();
  52. 	return temp;
  53. }
  54. int main()
  55. {
  56. 	struct tree *root = NULL;
  57. 	/*root = newNode();
  58. 	(root->child).push_back(newNode());
  59. 	(root->child).push_back(newNode());
  60.  
  61. 	(root->child[0]->child).push_back(newNode());
  62. 	(root->child[0]->child).push_back(newNode());
  63.  
  64. 	(root->child[1]->child).push_back(newNode());
  65.  
  66. 	(root->child[0]->child[1]->child).push_back(newNode());
  67. 	(root->child[0]->child[1]->child).push_back(newNode());
  68. 	*/
  69. 	root = newNode();
  70. 	(root->child).push_back(newNode());
  71. 	(root->child).push_back(newNode());
  72. 	(root->child).push_back(newNode());
  73.  
  74. 	(root->child[1]->child).push_back(newNode());
  75. 	(root->child[1]->child).push_back(newNode());
  76.  
  77. 	//(root->child[1]->child).push_back(newNode());
  78.  
  79. 	(root->child[1]->child[0]->child).push_back(newNode());
  80. 	(root->child[1]->child[0]->child).push_back(newNode());
  81.  
  82. 	(root->child[2]->child).push_back(newNode());
  83. 	(root->child[2]->child).push_back(newNode());
  84. 	(root->child[2]->child).push_back(newNode());
  85.  
  86.  
  87. 	printf("%d\n",vertex_cover(root));
  88.  
  89. }
Success #stdin #stdout 0s 2872KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4
https://ideone.com/L0Pfgm
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!