C++-এ ফ্লো নেটওয়ার্কে মিনিমাম s-t কাট (Minimum s-t Cut) বের করা

একটি ফ্লো নেটওয়ার্ক দেওয়া আছে। সোর্স s ও সিংক t আলাদা সাবসেটে থাকতে হবে এমন একটি কাট (cut) খুঁজে বের করতে হবে যাতে কাট-সেটের এজগুলোর ক্যাপাসিটির যোগফল ন্যূনতম হয়। ফোর্ড-ফালকারসন (এডমন্ডস-কার্প) অ্যালগরিদম ব্যবহার করা হয়।

অ্যালগরিদম

1. রিজিডুয়াল গ্রাফ বানান।
2. BFS দিয়ে অগমেন্টিং পাথ খুঁজুন (s থেকে t)।
3. পাথে মিনিমাম ক্যাপাসিটি (বটলনেক) বের করুন এবং রিজিডুয়াল ক্যাপাসিটি আপডেট করুন।
4. আর অগমেন্টিং পাথ না পাওয়া পর্যন্ত চালিয়ে যান।
5. ফাইনাল রিজিডুয়াল গ্রাফে s থেকে রিচযোগ্য নোডগুলো মার্ক করুন (DFS)।
6. যে এজগুলো রিচযোগ্য সেট থেকে নন-রিচযোগ্য সেটে যায়, সেগুলোই মিনিমাম কাট।

C++ প্রোগ্রাম

#include <bits/stdc++.h>
using namespace std;
#define NODES 6

bool bfs(int graph[NODES][NODES], int s, int t, int parent[]) {
    bool vis[NODES] = {0};
    queue<int> q; q.push(s);
    vis[s] = true; parent[s] = -1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v=0; v 0) {
                q.push(v); parent[v]=u; vis[v]=true;
            }
    }
    return vis[t];
}

void dfs(int graph[NODES][NODES], int u, bool vis[]) {
    vis[u] = true;
    for (int i=0;i
আউটপুট: (1, 3) (4, 3) (4, 5)