C++ প্রোগ্রাম: ডোমিনেটিং সেট সমস্যা সমাধান

এটি একটি C++ প্রোগ্রাম যা ডোমিনেটিং সেট সমস্যা সমাধান করে।

অ্যালগরিদম

শুরু
  ভার্টেক্স এবং এজের সংখ্যা ইনপুট নিন। এছাড়া এজের এন্ডপয়েন্টগুলোও নিন।
  ফাংশন dominant():
    ভেক্টর Set ডিক্লেয়ার করুন।
    গ্রাফের যেকোনো এজ e নিন যা ভার্টেক্স X এবং Y সংযুক্ত করে।
    X এবং Y-এর মাঝখানে একটি ভার্টেক্স সেট s-এ যোগ করুন।
    X-এর সাথে সংযুক্ত সব এজ ডিলিট করুন।
শেষ

উদাহরণ

#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;
    // গ্রাফের যেকোনো এজ e নিন যা ভার্টেক্স X এবং Y সংযুক্ত করে।
    for (i = 0; i < v; i++) {
        if (!visit[i]) {
            Set.push_back(i); // ভার্টেক্স যোগ করুন
            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)); // অ্যারে সব ইনডেক্সের মান ০ সেট করুন
    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