C++ Program to Solve the Dominating Set Problem - Computer Programming

# Computer Programming

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

## Tuesday, September 26, 2017

Write C++ Program to Solve the Dominating Set Problem

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

using namespace std;

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

vector<int> solve_dominant(int n,int e)
{
vector<int> S;
for(i=0;i<n;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<e;i++)
{
cout<<"Enter the end-points of edge "<<i+1<<" : ";
cin>>x>>y;
x--; y--;
graph[x].push_back(y);
graph[y].push_back(x);
}
vector<int> S = solve_dominant(n,e);
cout<<"The required Dominant Set is as follows:\n";
for(i=0;i<(int)S.size();i++)
cout<<S[i]+1<<" ";
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