রিডান্ডান্ট কানেকশন খুঁজে বের করা C++-এ (Union-Find)

সমস্যা বিবরণ

একটি ট্রি (N নোড, সাইকেল নেই) এর মধ্যে একটি অতিরিক্ত এজ যোগ করা হয়েছে। ফলে একটি সাইকেল তৈরি হয়েছে। সেই অতিরিক্ত এজটি খুঁজে বের করতে হবে যাতে সেটি মুছে ফেললে আবার ট্রি হয়ে যায়। একাধিক সমাধান থাকলে ইনপুটে সবচেয়ে পরে আসা এজটি রিটার্ন করুন।

উদাহরণ

ইনপুট: [[1,2], [2,3], [3,4], [1,4], [1,5]]

আউটপুট: [1,4] — এটি মুছে ফেললে ট্রি হয়ে যায়।

অ্যালগরিদম: Union-Find (Disjoint Set Union)

1. প্রতিটি নোডের প্যারেন্ট নিজে নিজে (অথবা -1)।
2. প্রতিটি এজ (u, v) জন্য:
   • find(u) ও find(v) করুন।
   • যদি প্যারেন্ট একই হয় → সাইকেল ডিটেক্ট হয়েছে → এই এজটি রিডান্ডান্ট।
   • অন্যথায় union(u, v) করুন (র‍্যাঙ্ক/সাইজ হিউরিস্টিক দিয়ে)।
3. ইনপুটে সবচেয়ে শেষে যে এজটি সাইকেল তৈরি করে, সেটি স্টোর করুন এবং রিটার্ন করুন।

C++ বাস্তবায়ন

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

const int N = 1000;

class Solution {
public:
    int parent[N + 5];
    int rank[N + 5];

    int findParent(int n) {
        if (parent[n] == -1) return n;
        return parent[n] = findParent(parent[n]);
    }

    bool unionn(int a, int b) {
        int pa = findParent(a);
        int pb = findParent(b);
        if (pa == pb) return false; // সাইকেল
        if (rank[pa] > rank[pb]) {
            rank[pa] += rank[pb];
            parent[pb] = pa;
        } else {
            rank[pb] += rank[pa];
            parent[pa] = pb;
        }
        return true;
    }

    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        for (int i = 0; i < n; i++) {
            parent[edges[i][0]] = parent[edges[i][1]] = -1;
            rank[edges[i][0]] = rank[edges[i][1]] = 1;
        }
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            int u = edges[i][0], v = edges[i][1];
            if (!unionn(u, v)) ans = edges[i];
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{1,2},{2,3},{3,4},{1,4},{1,5}};
    auto ans = ob.findRedundantConnection(v);
    cout << ans[0] << " " << ans[1]; // আউটপুট: 1 4
    return 0;
}

ইনপুট ও আউটপুট

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(N α(N)) ≈ O(N) — α হল ইনভার্স একার্মান ফাংশন, খুব ধীরে বড় হয়।
• স্থান জটিলতা: O(N) — প্যারেন্ট ও র‍্যাঙ্ক অ্যারে।