Aaj maine ek coding problem solve kiya hai jisme humein diya gaya tha ek undirected graph of n nodes jisme 3 types ke edges hai:

Type 1: Sirf Alice use kar sakti hai. 🧑‍🦱

Type 2: Sirf Bob use kar sakte hai. 🧑

Type 3: Dono Alice aur Bob use kar sakte hai. 🧑‍🤝‍🧑

Humko diya gaya tha ek array edges jisme edges[i] = [typei, ui, vi] represent karta hai ki node ui aur vi ke beech typei ke edge hai. Humein maximum number of edges nikalne hai jinhe hum remove kar sakte hai taaki graph fully traversable ho jaaye both Alice and Bob ke liye. Graph fully traversable tab mana jayega jab koi bhi node se start karke hum sabhi nodes tak pahuch sakte hai.

Agar hum koi edge remove karke bhi graph fully traversable nahi bana paate hai toh hum -1 return karenge.

Iss problem ka time complexity O(N) hai, jahaan N hai nodes ka count.

class Solution {
    public int maxNumEdgesToRemove(int n, int[][] edges) {
        UnionFind alice = new UnionFind(n);
        UnionFind bob = new UnionFind(n);
        int ans = 0;


        for (int[] e : edges) {
            if (e[0] == 3) {
                if (!alice.union(e[1]-1, e[2]-1)) {
                    ans++;
                }
                bob.union(e[1]-1, e[2]-1);
            }
        }


        for (int[] e : edges) {
            if (e[0] == 1) {
                if (!alice.union(e[1]-1, e[2]-1)) {
                    ans++;
                }
            }
        }


        for (int[] e : edges) {
            if (e[0] == 2) {
                if (!bob.union(e[1]-1, e[2]-1)) {
                    ans++;
                }
            }
        }


        if (alice.getCount() != 1 || bob.getCount() != 1) {
            return -1;
        }

        return ans;
    }
}

class UnionFind {
    private int[] parent;
    private int[] size;
    private int count;

    public UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        count = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public int find(int x) {
        if (x == parent[x]) {
            return x;
        }
        parent[x] = find(parent[x]);
        return parent[x];
    }

    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return false;
        }
        if (size[rootX] < size[rootY]) {
            int temp = rootX;
            rootX = rootY;
            rootY = temp;
        }
        parent[rootY] = rootX;
        size[rootX] += size[rootY];
        count--;
        return true;
    }

    public int getCount() {
        return count;
    }
}

#codingproblemsolved #graphtheory #leetcode #codinglife #hinglish #programming #codingbootcamp 🤓