지배적 집합 문제를 해결하기 위한 C++ 프로그램

이것은 Dominating Set 문제를 해결하기 위한 C++ 프로그램입니다.

알고리즘

Begin
   Take the number of vertices and edges as input. Also take the edge point of the edges.
   function dominant():
      Declare vector Set.
      Take any edge e graph connecting the vertices i.e.; X and Y.
      Add one vertex between X and Y to set s.
      Delete all the edges connected to X.
End

예시

#include<bits/stdc++.h>
using namespace std;
vector<vector<int> > g;
bool visit[10001];
int i,j;
vector<int> dominant(int v,int e) {
   vector<int> Set;
   //Take any edge e graph connecting the vertices i.e.; X and Y.
   for(i=0;i<v;i++) {
      if(!visit[i]) {
         Set.push_back(i); //Add vertex
         visit[i]=true;
         for(j=0;j<(int)g[i].size();j++) {
            if(!visit[g[i][j]]) {
               visit[g[i][j]]=true;
               break;
            }
         }
      }
   }
   return Set;
}
int main() {
   int v,e,a,b;
   cout<<"Enter number of vertices:";
   cin>>v;
   cout<<"Enter number of Edges:";
   cin>>e;
   g.resize(v);
   memset(visit,0,sizeof(visit)); //set all index value of an array as 0
   for(i=0;i<e;i++) {
      cout<<"Enter the end-points of edge "<<i+1<<" : ";
      cin>>a>>b;
      a--; b--;
      g[a].push_back(b);
      g[b].push_back(a);
   }
   vector<int> Set = dominant(v,e);
   cout<<"The Dominant Set is:\n";
   for(i=0;i<(int)Set.size();i++)
      cout<<Set[i]+1<<" ";
   return 0;
}

출력

Enter number of vertices:7
Enter number of Edges:6
Enter the end-points of edge 1 : 1 2
Enter the end-points of edge 2 : 2 2
Enter the end-points of edge 3 : 3 4
Enter the end-points of edge 4 : 4 5
Enter the end-points of edge 5 : 6 7
Enter the end-points of edge 6 : 4 5
The Dominant Set is:
1 3 5 6