সি++ প্রোগ্রাম: গ্রাফের ম্যাক্সিমাম কাট (Maximum Cut) বের করা

এই প্রোগ্রামে গ্রাফের ম্যাক্সিমাম কাট বের করতে হলে আমাদের সেই গ্রাফের এজ কানেক্টিভিটি (Edge Connectivity) বের করতে হবে। একটি গ্রাফের এজ কানেক্টিভিটি মানে এটি একটি ব্রিজ (bridge), যা রিমুভ করলে গ্রাফ ডিসকানেক্টেড হয়ে যাবে। একটি ডিসকানেক্টেড আনডিরেক্টেড গ্রাফে ব্রিজ রিমুভ করলে কানেক্টেড কম্পোনেন্টের সংখ্যা বেড়ে যায়।

ফাংশন এবং সুডোকোড

Begin
    Function connections() হলো একটি রিকার্সিভ ফাংশন কানেকশন খুঁজে বের করতে:
    A) বর্তমান নোডকে ভিজিটেড মার্ক করুন।
    B) টাইম এবং low মান ইনিশিয়ালাইজ করুন।
    C) এই নোডের সাথে সन्नিহিত সব ভার্টেক্স gennem যান।
    D) চেক করুন x-র সাথে রুট করা সাবট্রির w-এর আনসেস্টরের সাথে কানেকশন আছে কিনা।
       যদি x-র সাবট্রি থেকে পৌঁছানো যাবে সবচেয়ে নিচের ভার্টেক্স DFS ট্রিতে w-এর নিচে থাকে, তবে w-x-এর কানেকশন আছে।
    E) প্যারেন্ট ফাংশন কলের জন্য w-এর low মান আপডেট করুন।
End

Begin
    Function Con() যা connections() ব্যবহার করে:
    A) সব ভার্টেক্সকে আনভিজিটেড মার্ক করুন।
    B) par এবং visited, এবং connections ইনিশিয়ালাইজ করুন।
    C) গ্রাফের এজগুলোর মধ্যে কানেকশন প্রিন্ট করুন।
End

উদাহরণ

#include <iostream>
#include <list>
#define N -1
using namespace std;

class G {
    int n;
    list<int> *adj;
    void connections(int n, bool visited[], int disc[], int low[], int par[]);
public:
    G(int n); // কনস্ট্রাক্টর
    void addEd(int w, int x);
    void Con();
};

G::G(int n) {
    this->n = n;
    adj = new list<int>[n];
}

void G::addEd(int w, int x) {
    adj[x].push_back(w);
    adj[w].push_back(x);
}

void G::connections(int w, bool visited[], int dis[], int low[], int par[]) {
    static int t = 0;
    visited[w] = true;
    dis[w] = low[w] = ++t;
    list<int>::iterator i;
    for (i = adj[w].begin(); i != adj[w].end(); ++i) {
        int x = *i;
        if (!visited[x]) {
            par[x] = w;
            connections(x, visited, dis, low, par);
            low[w] = min(low[w], low[x]);
            if (low[x] > dis[w])
                cout << w << " " << x << endl;
        }
        else if (x != par[w])
            low[w] = min(low[w], dis[x]);
    }
}

void G::Con() {
    bool *visited = new bool[n];
    int *dis = new int[n];
    int *low = new int[n];
    int *par = new int[n];
    for (int i = 0; i < n; i++) {
        par[i] = N;
        visited[i] = false;
    }
    for (int i = 0; i < n; i++)
        if (visited[i] == false)
            connections(i, visited, dis, low, par);
}

int main() {
    cout << "\nConnections in first graph \n";
    G g1(5);
    g1.addEd(1, 2);
    g1.addEd(3, 2);
    g1.addEd(2, 1);
    g1.addEd(0, 1);
    g1.addEd(1, 4);
    g1.Con();
    return 0;
}

আউটপুট

Connections in first graph
2 3
1 2
1 4
0 1