#include <stdio.h>
#include <vector>
#include <algorithm>
#include <list>
#include <string.h>
#define MAX 10000
using namespace std;
vector <vector <int> > graph(MAX);
int nodes;
int edges;
list <int> req_vertices; //will store the vertices of minimum cover
int arr[MAX]; //vertex count
//here tree is represented as a graph
int minimum_vertex_cover(int root) //returns number of nodes
{
if(graph[root].size() == 0)
return 0;
if(arr[root] != -1)
return arr[root];
int with_root = 1;
for(int i = 0; i < (int) graph[root].size(); i++)
with_root += minimum_vertex_cover(graph[root][i]);
int without_root = graph[root].size();
for(int i = 0; i < (int) graph[root].size(); i++)
{
int present = graph[root][i];
for(int j = 0; j < (int) graph[present].size(); j++)
without_root += minimum_vertex_cover(graph[present][j]);
}
arr[root] = with_root < without_root ? with_root : without_root;
return arr[root];
}
int main()
{
int a, b;
printf("Enter number of nodes : ");
scanf("%d", &nodes);
memset(arr, -1, sizeof(arr));
printf("Enter number of edges : ");
scanf("%d", &edges);
printf("Enter the edges : ");
for(int i=0; i<edges; i++)
{
scanf("%d%d",&a,&b);
graph[a].push_back(b);
//graph[b].push_back(a);
}
printf("Number of nodes in vertex cover : %d\n",minimum_vertex_cover(0));
return 0;
}
CiNpbmNsdWRlIDxzdGRpby5oPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8bGlzdD4KI2luY2x1ZGUgPHN0cmluZy5oPgojZGVmaW5lIE1BWCAxMDAwMAoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCgp2ZWN0b3IgPHZlY3RvciA8aW50PiA+IGdyYXBoKE1BWCk7CmludCBub2RlczsKaW50IGVkZ2VzOwpsaXN0IDxpbnQ+IHJlcV92ZXJ0aWNlczsJLy93aWxsIHN0b3JlIHRoZSB2ZXJ0aWNlcyBvZiBtaW5pbXVtIGNvdmVyCgppbnQgYXJyW01BWF07CQkJLy92ZXJ0ZXggY291bnQKCi8vaGVyZSB0cmVlIGlzIHJlcHJlc2VudGVkIGFzIGEgZ3JhcGggCmludCBtaW5pbXVtX3ZlcnRleF9jb3ZlcihpbnQgcm9vdCkJLy9yZXR1cm5zIG51bWJlciBvZiBub2Rlcwp7CglpZihncmFwaFtyb290XS5zaXplKCkgPT0gMCkJCgkJcmV0dXJuIDA7CQoJaWYoYXJyW3Jvb3RdICE9IC0xKQoJCXJldHVybiBhcnJbcm9vdF07CQoJCglpbnQgd2l0aF9yb290ID0gMTsKCQoJZm9yKGludCBpID0gMDsgaSA8IChpbnQpIGdyYXBoW3Jvb3RdLnNpemUoKTsgaSsrKQoJCXdpdGhfcm9vdCArPSBtaW5pbXVtX3ZlcnRleF9jb3ZlcihncmFwaFtyb290XVtpXSk7CgkJCglpbnQgd2l0aG91dF9yb290ID0gZ3JhcGhbcm9vdF0uc2l6ZSgpOwoJCglmb3IoaW50IGkgPSAwOyBpIDwgKGludCkgZ3JhcGhbcm9vdF0uc2l6ZSgpOyBpKyspCQoJewoJCWludCBwcmVzZW50ID0gZ3JhcGhbcm9vdF1baV07CgkJZm9yKGludCBqID0gMDsgaiA8IChpbnQpIGdyYXBoW3ByZXNlbnRdLnNpemUoKTsgaisrKQoJCQl3aXRob3V0X3Jvb3QgKz0gbWluaW11bV92ZXJ0ZXhfY292ZXIoZ3JhcGhbcHJlc2VudF1bal0pOwoJfSAgCgkKCWFycltyb290XSA9IHdpdGhfcm9vdCA8IHdpdGhvdXRfcm9vdCA/IHdpdGhfcm9vdCA6IHdpdGhvdXRfcm9vdDsKCQoJcmV0dXJuIGFycltyb290XTsKCQp9CgppbnQgbWFpbigpCnsKCWludCBhLCBiOwoJcHJpbnRmKCJFbnRlciBudW1iZXIgb2Ygbm9kZXMgOiAiKTsKCXNjYW5mKCIlZCIsICZub2Rlcyk7CgkKCW1lbXNldChhcnIsIC0xLCBzaXplb2YoYXJyKSk7CgkKCXByaW50ZigiRW50ZXIgbnVtYmVyIG9mIGVkZ2VzIDogIik7CglzY2FuZigiJWQiLCAmZWRnZXMpOwoJcHJpbnRmKCJFbnRlciB0aGUgZWRnZXMgOiAiKTsKCWZvcihpbnQgaT0wOyBpPGVkZ2VzOyBpKyspCgl7CgkJc2NhbmYoIiVkJWQiLCZhLCZiKTsKCQlncmFwaFthXS5wdXNoX2JhY2soYik7CgkJLy9ncmFwaFtiXS5wdXNoX2JhY2soYSk7Cgl9CgkKCXByaW50ZigiTnVtYmVyIG9mIG5vZGVzIGluIHZlcnRleCBjb3ZlciA6ICVkXG4iLG1pbmltdW1fdmVydGV4X2NvdmVyKDApKTsKCQoJCgkKCXJldHVybiAwOwp9