C++ Program to Solve the Dominating Set Problem

Code:

#include     bits/stdc++.h

using namespace std;

vector > graph;
bool vis[100011];
int i,j;

vector solve_dominant(int n,int e)
{
vector S;
for(i=0;i
{
if(!vis[i])
{
S.push_back(i);
vis[i]=true;
for(j=0;j<(int)graph[i].size();j++)
{
if(!vis[graph[i][j]])
{
vis[graph[i][j]]=true;
break;
}
}
}
}
return S;
}
int main()
{
int n,e,x,y;
cout<<"Enter number of vertices:";
cin>>n;
cout<<"Enter number of Edges:";
cin>>e;
graph.resize(n);
memset(vis,0,sizeof(vis));
for(i=0;i
{
cout<<"Enter the end-points of edge "<
cin>>x>>y;
x--; y--;
graph[x].push_back(y);
graph[y].push_back(x);
}
vector S = solve_dominant(n,e);
cout<<"The required Dominant Set is as follows:\n";
for(i=0;i<(int)S.size();i++)
cout<
return 0;
}


Output:

Enter number of vertices:5
Enter number of Edges:6
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 end-points of edge 5 : 4 5
Enter the end-points of edge 6 : 3 5
The required Dominant Set is as follows:
1 3 5 

Case 2:
Enter number of vertices:4
Enter number of Edges:3
Enter the end-points of edge 1 : 1 2
Enter the end-points of edge 2 : 1 3
Enter the end-points of edge 3 : 3 4
The required Dominant Set is as follows:
1 3



More C++ Programs: