C++ Program to Check Whether a Vertex Cover of Size k Exists - Computer Programming

Latest

C C++ Java Python Perl Programs Examples with Output -useful for Schools & College Students

Tuesday, September 26, 2017

C++ Program to Check Whether a Vertex Cover of Size k Exists

Write a C++ Program to Check Whether a Vertex Cover of Size k Exists

Program:
#include<bits/stdc++.h>

using namespace std;

bool graph[1001][1001];
bool vis[1001][1001];

int i,j,k,v;
int n,e,x,y;

bool isVertexCover(int sz)
{
int c,r,cnt=0;
int set = (1 << sz) - 1;
int limit = (1 << n);
while (set < limit)
{
memset(vis,0,sizeof(vis));
cnt = 0;
for (j = 1, v = 1 ; j < limit ; j = j << 1, v++)
{
if (set & j)
{
for (k = 0 ; k <= n-1 ; k++)
{
if (graph[v][k] && !vis[v][k])
{
vis[v][k] = 1;
vis[k][v] = 1;
cnt++;
}
}
}
}
if (cnt == e)
return true;
c = set & -set;
r = set + c;
set = (((r^set) >> 2) / c) | r;
}
return false;
}

int main()
{
cout<<"Enter number of vertices:";
cin>>n;
cout<<"\nEnter number of Edges:";
cin>>e;
for(i=0;i<e;i++)
{
cout<<"Enter the end-points of edge "<<i+1<<":";
cin>>x>>y;
x--; y--;
graph[x][y]=1;
graph[y][x]=1;
}
cout<<"Enter the size of Vertex Cover to check for (should be less than number of vertices) :";
cin>>k;
if(isVertexCover(k))
cout<<"Vertex Cover of size"<<" "<<k<<" exist.\n";
else
cout<<"Vertex Cover of size"<<" "<<k<<" does not exist.\n";
return 0;
}

Output:
Enter number of vertices:4

Enter number of Edges:4
Enter the end-points of edge 1:1 2
Enter the end-points of edge 2:2 3
Enter the end-points of edge 3:3 4
Enter the end-points of edge 4:1 4
Enter the size of Vertex Cover to check for:1

Vertex Cover of size 1 does not exist.

No comments:

Post a Comment