Detailed Video + Solution | Java C++ Python
\n\n\nclass UnionFind {\n    private int[] parent;\n\n    public UnionFind(int n) {\n        parent = new int[n];\n        for (int i = 0; i < n; i++)\n        
<iframe width="560" height="315" src="https://www.youtube.com/embed/u1-Xuvl2RoA" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>\n\n```\nclass UnionFind {\n    private int[] parent;\n\n    public UnionFind(int n) {\n        parent = new int[n];\n        for (int i = 0; i < n; i++)\n            parent[i] = i;\n    }\n\n    public int findParent(int p) {\n        return parent[p] == p ? p : (parent[p] = findParent(parent[p]));\n    }\n\n    public void union(int u, int v) {\n        int pu = findParent(u), pv = findParent(v);\n        parent[pu] = pv;\n    }\n}\n\nclass Solution {\n    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {\n        List<Integer> critical = new ArrayList<>();\n        List<Integer> pseudoCritical = new ArrayList<>();\n        \n        for (int i = 0; i < edges.length; i++) {\n            int[] edge = edges[i];\n            edge = Arrays.copyOf(edge, edge.length + 1);\n            edge[3] = i;\n            edges[i] = edge;\n        }\n        \n        Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));\n\n        int mstwt = findMST(n, edges, -1, -1);\n\n        for (int i = 0; i < edges.length; i++) {\n            if (mstwt < findMST(n, edges, i, -1))\n                critical.add(edges[i][3]);\n            else if (mstwt == findMST(n, edges, -1, i))\n                pseudoCritical.add(edges[i][3]);\n        }\n\n        List<List<Integer>> result = new ArrayList<>();\n        result.add(critical);\n        result.add(pseudoCritical);\n        return result;\n    }\n\n    private int findMST(int n, int[][] edges, int block, int e) {\n        UnionFind uf = new UnionFind(n);\n        int weight = 0;\n\n        if (e != -1) {\n            weight += edges[e][2];\n            uf.union(edges[e][0], edges[e][1]);\n        }\n\n        for (int i = 0; i < edges.length; i++) {\n            if (i == block)\n                continue;\n\n            if (uf.findParent(edges[i][0]) == uf.findParent(edges[i][1]))\n                continue;\n\n            uf.union(edges[i][0], edges[i][1]);\n            weight += edges[i][2];\n        }\n\n        for (int i = 0; i < n; i++) {\n            if (uf.findParent(i) != uf.findParent(0))\n                return Integer.MAX_VALUE;\n        }\n\n        return weight;\n    }\n}\n```\n\n```\nclass UnionFind {\nprivate:\n    vector<int> parent;\n\npublic:\n    UnionFind(int n) {\n        parent.resize(n);\n        for (int i = 0; i < n; i++)\n            parent[i] = i;\n    }\n\n    int findParent(int p) {\n        return parent[p] == p ? p : (parent[p] = findParent(parent[p]));\n    }\n\n    void unionSets(int u, int v) {\n        int pu = findParent(u), pv = findParent(v);\n        parent[pu] = pv;\n    }\n};\n\nclass Solution {\npublic:\n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {\n        vector<int> critical;\n        vector<int> pseudoCritical;\n        \n        for (int i = 0; i < edges.size(); i++) {\n            edges[i].push_back(i);\n        }\n        \n        sort(edges.begin(), edges.end(), [](const vector<int>& a, const vector<int>& b) {\n            return a[2] < b[2];\n        });\n\n        int mstwt = findMST(n, edges, -1, -1);\n\n        for (int i = 0; i < edges.size(); i++) {\n            if (mstwt < findMST(n, edges, i, -1))\n                critical.push_back(edges[i][3]);\n            else if (mstwt == findMST(n, edges, -1, i))\n                pseudoCritical.push_back(edges[i][3]);\n        }\n\n        vector<vector<int>> result;\n        result.push_back(critical);\n        result.push_back(pseudoCritical);\n        return result;\n    }\n\n    int findMST(int n, vector<vector<int>>& edges, int block, int e) {\n        UnionFind uf(n);\n        int weight = 0;\n\n        if (e != -1) {\n            weight += edges[e][2];\n            uf.unionSets(edges[e][0], edges[e][1]);\n        }\n\n        for (int i = 0; i < edges.size(); i++) {\n            if (i == block)\n                continue;\n\n            if (uf.findParent(edges[i][0]) == uf.findParent(edges[i][1]))\n                continue;\n\n            uf.unionSets(edges[i][0], edges[i][1]);\n            weight += edges[i][2];\n        }\n\n        for (int i = 0; i < n; i++) {\n            if (uf.findParent(i) != uf.findParent(0))\n                return INT_MAX;\n        }\n\n        return weight;\n    }\n};\n```\n\n```\nclass UnionFind:\n    def __init__(self, n):\n        self.parent = list(range(n))\n        \n    def find_parent(self, p):\n        if self.parent[p] != p:\n            self.parent[p] = self.find_parent(self.parent[p])\n        return self.parent[p]\n    \n    def union_sets(self, u, v):\n        pu, pv = self.find_parent(u), self.find_parent(v)\n        self.parent[pu] = pv\n\nclass Solution:\n    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n        def find_MST(graph, block, e):\n            uf = UnionFind(n)\n            weight = 0\n            \n            if e != -1:\n                weight += edges[e][2]\n                uf.union_sets(edges[e][0], edges[e][1])\n            \n            for i in range(len(edges)):\n                if i == block:\n                    continue\n                \n                if uf.find_parent(edges[i][0]) == uf.find_parent(edges[i][1]):\n                    continue\n                \n                uf.union_sets(edges[i][0], edges[i][1])\n                weight += edges[i][2]\n            \n            for i in range(n):\n                if uf.find_parent(i) != uf.find_parent(0):\n                    return float(\'inf\')\n            \n            return weight\n        \n        critical = []\n        pseudo_critical = []\n        \n        for i, edge in enumerate(edges):\n            edge.append(i)\n        \n        edges.sort(key=lambda x: x[2])\n        mst_weight = find_MST(edges, -1, -1)\n        \n        for i, edge in enumerate(edges):\n            if mst_weight < find_MST(edges, i, -1):\n                critical.append(edge[3])\n            elif mst_weight == find_MST(edges, -1, i):\n                pseudo_critical.append(edge[3])\n        \n        return [critical, pseudo_critical]\n\n```
['C', 'Python', 'Java']