🔥🔥🔥🔥🔥Beats 100% | JS | TS | Java | C++ | C# | Python | python3 | Kotlin | 🔥🔥🔥🔥🔥
---\n\n\n---\n\n### Problem Explanation:\n\nThe problem you\'re solving is related to Minimum Spanning Trees (MSTs). You\'re asked to classify the edges of a gr
---\n![header_.png](https://assets.leetcode.com/users/images/ab4510d5-90e7-4616-b1e1-aac91ec90eea_1692159981.2067795.png)\n\n---\n\n### Problem Explanation:\n\nThe problem you\'re solving is related to Minimum Spanning Trees (MSTs). You\'re asked to classify the edges of a graph into two categories: **critical** and **pseudo-critical** edges.\n\n- **Critical Edges**: These are the edges that must be part of every possible MST. Removing these edges from the graph increases the MST weight.\n- **Pseudo-Critical Edges**: These edges can be included in the MST without affecting the overall weight of the MST. They are part of some, but not all, MSTs.\n\nGiven `n` nodes and `edges`, where each edge connects two nodes with a certain weight, the goal is to determine which edges are critical and which are pseudo-critical.\n\n### Approach:\n\nThe approach to solving this problem involves using **Kruskal\'s algorithm** for MSTs and exploring the role of each edge by simulating its presence or absence in the MST construction process.\n\n1. **Step 1**: Find the MST for the graph using Kruskal\u2019s algorithm. This MST will give the minimum weight.\n2. **Step 2**: For each edge:\n    - **Critical Check**: Remove the edge and compute the MST without it. If the MST weight increases, then this edge is **critical**.\n    - **Pseudo-Critical Check**: Force the inclusion of the edge at the beginning of the MST. If the MST weight remains the same, then this edge is **pseudo-critical**.\n\n### Key Concepts:\n\n- **Union-Find/Disjoint Set**: This data structure helps in determining whether two nodes belong to the same component. It\'s used to construct the MST efficiently.\n- **Kruskal\u2019s Algorithm**: A greedy algorithm to find the MST. It sorts all edges by weight and adds them one by one to the MST while avoiding cycles using the Union-Find structure.\n  \n### Solution Breakdown:\n\n1. **Union-Find Class**: \n   - This class helps maintain and merge the connected components of nodes in the graph.\n   - `findParent(p)` finds the root of a node, applying path compression to make future queries faster.\n   - `union(u, v)` merges the components containing `u` and `v`.\n\n2. **Main Algorithm**:\n   - **Sorting Edges**: First, edges are sorted by weight to apply Kruskal\'s algorithm.\n   - **MST Calculation**: The function `findMST` is used to compute the MST weight. You can block an edge (remove it) or force an edge (add it upfront).\n   - **Critical and Pseudo-Critical Check**:\n     - For each edge, you calculate two alternative MSTs:\n       1. **Without the edge**: If the MST weight increases, the edge is critical.\n       2. **With the edge forcibly included**: If the MST weight remains the same, the edge is pseudo-critical.\n\n### Code Explanation (C++ Version):\n\n- **Union-Find Class**: Implements the `findParent` and `union` operations to track and merge components during MST construction.\n  \n- **findCriticalAndPseudoCriticalEdges Function**:\n  - First, a reference MST is calculated using all edges.\n  - Then, for each edge:\n    - Calculate the MST without that edge (critical check).\n    - Calculate the MST with that edge forcibly included (pseudo-critical check).\n\n- **findMST Function**:\n  - Implements Kruskal\'s algorithm to find the MST.\n  - You can skip an edge (for critical check) or include an edge upfront (for pseudo-critical check).\n  - The function ensures all nodes are connected; otherwise, the graph isn\'t fully connected, and the result is invalid.\n\n### Complexity:\n- **Time Complexity**: Sorting the edges takes \\(O(E \\log E)\\), and each MST computation involves Union-Find operations on \\(n\\) nodes and \\(E\\) edges, leading to an overall complexity of \\(O(E \\log E + E \\cdot \\alpha(n))\\), where \\(\\alpha(n)\\) is the inverse Ackermann function, which is nearly constant.\n- **Space Complexity**: The space complexity is \\(O(n + E)\\) due to the Union-Find data structure and storing the edges.\n\n### Conclusion:\nThis approach efficiently classifies the edges into critical and pseudo-critical categories using MST properties and the Union-Find data structure. By simulating edge removal or inclusion, you determine the role of each edge in the MST.\n\n---\n```C++ []\n// Union-Find (Disjoint Set) class to manage connected components\nclass UnionFind {\npublic: \n    vector<int> parent;  // Parent array to store parent of each node\n\n    // Constructor to initialize parent array with self-references\n    UnionFind(int n){\n        parent.resize(n);  // Resize parent vector to size n\n        for(int i = 0; i < n; i++)\n            parent[i] = i;  // Each node is its own parent (initially self-referenced)\n    }\n    \n    // Find the root/parent of node p with path compression\n    int findParent(int p) {\n        // If parent of p is p itself, return p, otherwise recursively find the parent and compress the path\n        return parent[p] == p ? p : parent[p] = findParent(parent[p]); \n    }\n    \n    // Union operation: Join two components (u and v) by connecting their roots\n    void Union(int u, int v) {\n        int pu = findParent(u);  // Find root of u\n        int pv = findParent(v);  // Find root of v\n        parent[pu] = pv;  // Set root of u to be root of v, effectively joining the sets\n    }    \n};\n\n// Solution class to find critical and pseudo-critical edges in a graph\nclass Solution {\npublic:\n    // Comparator function to sort edges based on their weights (ascending order)\n    static bool cmp(vector<int>&a, vector<int>&b) {\n        return a[2] < b[2];  // Compare the third element (weight) of the two edges\n    }\n    \n    // Main function to find critical and pseudo-critical edges\n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {\n        vector<int> critical, pscritical;  // Vectors to store critical and pseudo-critical edges\n        \n        // 1. Append the original index of each edge to the edge vector for future reference\n        for(int i = 0; i < edges.size(); i++)\n            edges[i].push_back(i);  // Add edge index as the 4th element\n        \n        // 2. Sort edges based on their weight using the custom comparator\n        sort(edges.begin(), edges.end(), cmp);\n        \n        // 3. Find the weight of the Minimum Spanning Tree (MST) without excluding any edge\n        int mstwt = findMST(n, edges, -1, -1);  // No edge is blocked (-1), no edge is pre-included (-1)\n        \n        // Loop through all edges to check if they are critical or pseudo-critical\n        for(int i = 0; i < edges.size(); i++) {\n            // 5. Check if excluding the edge results in a different MST weight\n            // If the weight of MST without this edge is greater, it is a critical edge\n            if(mstwt < findMST(n, edges, i, -1))  // i-th edge is blocked\n                critical.push_back(edges[i][3]);  // Add the original index of this edge to critical list\n            // 6. Check if pre-including the edge results in the same MST weight\n            // If the weight remains the same, it is a pseudo-critical edge\n            else if(mstwt == findMST(n, edges, -1, i))  // i-th edge is pre-included\n                pscritical.push_back(edges[i][3]);  // Add the original index of this edge to pseudo-critical list\n        }\n        return {critical, pscritical};  // Return the two lists as a result\n    }\n    \nprivate:\n    // Function to find the weight of the MST\n    // block: Edge to exclude, e: Edge to pre-include in the MST\n    int findMST(int &n, vector<vector<int>>& edges, int block, int e) {\n        UnionFind uf(n);  // Initialize Union-Find structure for n nodes\n        int weight = 0;   // Variable to store total MST weight\n        \n        // If an edge (e) is pre-included, add its weight and union its endpoints\n        if(e != -1) {\n            weight += edges[e][2];  // Add weight of the pre-included edge\n            uf.Union(edges[e][0], edges[e][1]);  // Union the two nodes of the pre-included edge\n        }\n        \n        // Loop through all edges to construct the MST, skipping the blocked edge\n        for(int i = 0; i < edges.size(); i++) {\n            if(i == block) \n                continue;  // Skip the blocked edge\n            // If the two nodes of the current edge are already connected, skip this edge (to avoid cycles)\n            if(uf.findParent(edges[i][0]) == uf.findParent(edges[i][1])) \n                continue; \n            // Otherwise, union the nodes and add the edge\'s weight to the MST\n            uf.Union(edges[i][0], edges[i][1]); \n            weight += edges[i][2];  // Add edge\'s weight to total MST weight\n        }\n        \n        // Check if all nodes are included in the MST (i.e., connected)\n        for(int i = 0; i < n; i++) {\n            // If any node is not connected to the component containing node 0, return a large value\n            if(uf.findParent(i) != uf.findParent(0))\n                return INT_MAX;  // Indicates the MST is incomplete or invalid\n        }    \n        \n        return weight;  // Return the total weight of the MST\n    }\n    \n};\n\n```\n```Typescript []\nfunction findCriticalAndPseudoCriticalEdges(n: number, edges: number[][]): number[][] {\n    // Create a shallow copy of the edges to avoid mutating the original array\n    let copyEdges = [...edges];\n    \n    // Find the MST (Minimum Spanning Tree) weight without forcing or deleting any edge\n    let mst = findMst(n, copyEdges, [], []);\n    \n    // Arrays to store critical and pseudo-critical edges\n    let critical: number[] = [];\n    let pseudoCritical: number[] = [];\n    \n    // Iterate through each edge to determine if it is critical or pseudo-critical\n    for (let i = 0; i < edges.length; i++) {\n        \n        // Try to find the MST without the current edge\n        let delMst = findMst(n, copyEdges, [], edges[i]);\n        \n        // If the MST changes (i.e., gets worse), the current edge is critical\n        if (delMst != mst) {\n            critical.push(i);\n            continue;  // Move to the next edge\n        }\n\n        // Try to find the MST with the current edge forced to be included\n        let forceMst = findMst(n, copyEdges, edges[i], []);\n        \n        // If the MST is the same with the current edge, it\'s pseudo-critical\n        if (forceMst == mst)\n            pseudoCritical.push(i);\n    }\n\n    // Return both critical and pseudo-critical edges\n    return [critical, pseudoCritical];\n}\n\n// Helper function to filter out a specific row from a 2D array (used to remove an edge)\nfunction filterRow(rowNum: number, arr: number[][]): number[][] {\n    let copy: number[][] = [];\n    \n    // Iterate over the array and copy all rows except the one at rowNum\n    for (let i = 0; i < arr.length; i++)\n        if (i != rowNum)\n            copy.push(arr[i]);\n    \n    return copy;\n}\n\n// Function to find the weight of the MST (Minimum Spanning Tree)\n// It optionally forces an edge to be included or deletes an edge from the MST calculation\nfunction findMst(n: number, edges: number[][], forceEdge: number[], deleteEdge: number[]): number {\n    // Sort the edges based on their weights in ascending order\n    edges.sort((a, b) => a[2] - b[2]);\n\n    // Initialize the parent and rank arrays for union-find (disjoint set)\n    const parent = Array(n);\n    const rank = Array(n).fill(0);\n    \n    // Set each node\'s parent to itself initially (disjoint set)\n    for (let i = 0; i < n; i++)\n        parent[i] = i;\n\n    let mst: number = 0;  // Total weight of the MST\n    let numEdges: number = 0;  // Number of edges included in the MST so far\n\n    // If there is a forced edge to include, add it first\n    if (forceEdge.length != 0) {\n        let edge = forceEdge;\n        let v1 = edge[0];\n        let v2 = edge[1];\n        let weight = edge[2];\n        \n        // If v1 and v2 are not already connected, add this edge to the MST\n        if (findParent(v1, parent) != findParent(v2, parent)) {\n            numEdges++;\n            mst += weight;\n            union(v1, v2, rank, parent);\n        }\n    }\n\n    // Now, process the rest of the edges in the sorted list\n    for (let i = 0; i < edges.length; i++) {\n        let edge = edges[i];\n        let v1 = edge[0];\n        let v2 = edge[1];\n        let weight = edge[2];\n        \n        // Skip the edge if it\'s the one to be deleted\n        if (deleteEdge.length != 0 && v1 == deleteEdge[0] && v2 == deleteEdge[1])\n            continue;\n\n        // If v1 and v2 are not already connected, add this edge to the MST\n        if (findParent(v1, parent) != findParent(v2, parent)) {\n            numEdges++;\n            mst += weight;\n            union(v1, v2, rank, parent);\n        }\n\n        // If we already have n-1 edges, the MST is complete\n        if (numEdges == n - 1)\n            break;\n    }\n\n    return mst;  // Return the total weight of the MST\n}\n\n// Function to find the parent of a vertex in the disjoint set (with path compression)\nfunction findParent(vertex: number, parent: number[]): number {\n    // If the parent of the vertex is itself, return it\n    if (parent[vertex] == vertex)\n        return vertex;\n    \n    // Recursively find the parent and apply path compression\n    return parent[vertex] = findParent(parent[vertex], parent);\n}\n\n// Function to union two sets (vertices) by rank\nfunction union(v1: number, v2: number, rank: number[], parent: number[]): void {\n    v1 = findParent(v1, parent);\n    v2 = findParent(v2, parent);\n    \n    // Union by rank: attach the smaller tree under the larger one\n    if (rank[v1] > rank[v2]) {\n        parent[v2] = v1;\n    } else if (rank[v2] > rank[v1]) {\n        parent[v1] = v2;\n    } else {\n        // If ranks are the same, increment the rank of v1 and attach v2 under v1\n        parent[v2] = v1;\n        rank[v1]++;\n    }\n}\n\n```\n```Java []\nimport java.util.*;\n\n// Union-Find class to handle the connected components for Kruskal\'s algorithm\nclass UnionFind {\n    private int[] parent;\n\n    // Constructor initializes the Union-Find structure with `n` nodes\n    public UnionFind(int n) {\n        parent = new int[n];\n        // Initially, each node is its own parent (each node is its own component)\n        for (int i = 0; i < n; i++)\n            parent[i] = i;\n    }\n\n    // Find operation with path compression\n    // This function finds the representative (parent) of a node `p`\n    public int findParent(int p) {\n        // Path compression optimization: make the parent of each node point to the root directly\n        return parent[p] == p ? p : (parent[p] = findParent(parent[p]));\n    }\n\n    // Union operation: connects two components by linking their roots\n    public void union(int u, int v) {\n        int pu = findParent(u), pv = findParent(v);\n        // Make the parent of one root point to the other, effectively connecting the two components\n        parent[pu] = pv;\n    }\n}\n\n// Solution class to find critical and pseudo-critical edges in a Minimum Spanning Tree (MST)\nclass Solution {\n    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {\n        List<Integer> critical = new ArrayList<>();         // List to store critical edges\n        List<Integer> pseudoCritical = new ArrayList<>();   // List to store pseudo-critical edges\n        \n        // Add the original index of each edge to the edge array to track them after sorting\n        for (int i = 0; i < edges.length; i++) {\n            int[] edge = edges[i];\n            edge = Arrays.copyOf(edge, edge.length + 1); // Extend the edge array to hold the index\n            edge[3] = i; // Store the original index of the edge\n            edges[i] = edge; // Update the edge array\n        }\n        \n        // Sort edges by their weight in ascending order\n        Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));\n\n        // Find the weight of the Minimum Spanning Tree (MST\n```\n```Python []\nclass UnionFind:\n    # Constructor to initialize the UnionFind (Disjoint Set) structure\n    def __init__(self, n):\n        # Initialize each node to be its own parent (self-loop)\n        self.parent = list(range(n))\n    \n    # Method to find the root (parent) of a node with path compression\n    def find_parent(self, p):\n        # If the node is its own parent, return it\n        if self.parent[p] == p:\n            return p\n        # Path compression: make the parent of p the root of the set\n        self.parent[p] = self.find_parent(self.parent[p])\n        return self.parent[p]\n    \n    # Method to unify two nodes by connecting their sets\n    def union(self, u, v):\n        # Find the root of u and the root of v\n        pu, pv = self.find_parent(u), self.find_parent(v)\n        # Merge the two sets by making one root the parent of the other\n        self.parent[pu] = pv\n\nclass Solution:\n    # A static method to compare two edges based on their weights (used in sorting)\n    @staticmethod\n    def cmp(a, b):\n        return a[2] < b[2]  # Compare based on the weight (third element of the edge)\n    \n    # Method to find critical and pseudo-critical edges in the Minimum Spanning Tree (MST)\n    def findCriticalAndPseudoCriticalEdges(self, n, edges):\n        critical = []  # List to store critical edges\n        pseudo_critical = []  # List to store pseudo-critical edges\n        \n        # Add an index to each edge to track its original position\n        for i in range(len(edges)):\n            edges[i].append(i)\n        \n        # Sort the edges based on their weights\n        edges.sort(key=lambda x: x[2])\n        \n        # Find the total weight of the Minimum Spanning Tree (MST) without any exclusions\n        mstwt = self.find_MST(n, edges, -1, -1)\n        \n        # Iterate over all edges to find critical and pseudo-critical ones\n        for i in range(len(edges)):\n            # Check if excluding this edge increases the MST weight (i.e., it\'s critical)\n            if mstwt < self.find_MST(n, edges, i, -1):\n                critical.append(edges[i][3])  # Append the index of the critical edge\n            # Check if including this edge keeps the MST weight the same (i.e., it\'s pseudo-critical)\n            elif mstwt == self.find_MST(n, edges, -1, i):\n                pseudo_critical.append(edges[i][3])  # Append the index of the pseudo-critical edge\n        \n        # Return the list of critical and pseudo-critical edges\n        return [critical, pseudo_critical]\n    \n    # Helper method to find the weight of the MST\n    # \'block\' is the edge to exclude, \'e\' is the edge to force include\n    def find_MST(self, n, edges, block, e):\n        uf = UnionFind(n)  # Initialize the UnionFind structure for \'n\' nodes\n        weight = 0  # Initialize the total weight of the MST\n        \n        # If \'e\' is not -1, include that edge first\n        if e != -1:\n            weight += edges[e][2]  # Add the weight of the edge \'e\'\n            uf.union(edges[e][0], edges[e][1])  # Union the nodes of edge \'e\'\n        \n        # Iterate through all edges to build the MST\n        for i in range(len(edges)):\n            # Skip the blocked edge\n            if i == block:\n                continue\n            # If the edge forms a cycle, skip it\n            if uf.find_parent(edges[i][0]) == uf.find_parent(edges[i][1]):\n                continue\n            # Otherwise, union the nodes and add the edge weight to the total\n            uf.union(edges[i][0], edges[i][1])\n            weight += edges[i][2]\n        \n        # Check if all nodes are connected (i.e., the graph forms a spanning tree)\n        for i in range(n):\n            if uf.find_parent(i) != uf.find_parent(0):\n                return float(\'inf\')  # If not all nodes are connected, return infinity\n        \n        # Return the total weight of the MST\n        return weight\n```\n```Python3 []\nclass UnionFind:\n    # Constructor to initialize the Union-Find structure with n elements.\n    def __init__(self, n):\n        # Each element is its own parent initially.\n        self.parent = list(range(n))\n    \n    # Find function with path compression optimization.\n    # This function returns the root parent of the element p.\n    def find_parent(self, p):\n        # If the element is its own parent, return it.\n        if self.parent[p] == p:\n            return p\n        # Otherwise, recursively find the root parent and compress the path.\n        self.parent[p] = self.find_parent(self.parent[p])\n        return self.parent[p]\n    \n    # Union function to merge two sets (u and v).\n    def union(self, u, v):\n        # Find the root parents of u and v.\n        pu, pv = self.find_parent(u), self.find_parent(v)\n        # Make the root of u point to the root of v (merge them).\n        self.parent[pu] = pv\n\nclass Solution:\n    # Main function to find critical and pseudo-critical edges in a graph.\n    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n        # Helper function to compare edges based on weight.\n        def cmp(a, b):\n            return a[2] < b[2]  # Compare the third element (weight) of each edge.\n        \n        critical, pseudo_critical = [], []  # To store critical and pseudo-critical edges.\n        \n        # Append index of each edge to keep track of their original position.\n        for i in range(len(edges)):\n            edges[i].append(i)\n        \n        # Sort edges by weight.\n        edges.sort(key=lambda x: x[2])\n        \n        # Find the weight of the minimum spanning tree (MST) without blocking any edge.\n        mst_wt = self.find_mst(n, edges, -1, -1)\n        \n        # Iterate through each edge to determine if it\'s critical or pseudo-critical.\n        for i in range(len(edges)):\n            # If excluding this edge results in a higher MST weight, it\'s critical.\n            if mst_wt < self.find_mst(n, edges, i, -1):\n                critical.append(edges[i][3])  # Append the original index of the edge.\n            # If including this edge results in the same MST weight, it\'s pseudo-critical.\n            elif mst_wt == self.find_mst(n, edges, -1, i):\n                pseudo_critical.append(edges[i][3])  # Append the original index of the edge.\n        \n        # Return the list of critical and pseudo-critical edges.\n        return [critical, pseudo_critical]\n    \n    # Function to find the weight of the MST, optionally blocking or forcing an edge.\n    def find_mst(self, n, edges, block, e):\n        # Initialize the Union-Find structure for n nodes.\n        uf = UnionFind(n)\n        weight = 0  # Track the total weight of the MST.\n        \n        # If edge \'e\' is forced, add it to the MST.\n        if e != -1:\n            weight += edges[e][2]  # Add the weight of the forced edge.\n            uf.union(edges[e][0], edges[e][1])  # Union the vertices of the forced edge.\n        \n        # Iterate through all edges to construct the MST.\n        for i in range(len(edges)):\n            # Skip the edge if it\'s blocked.\n            if i == block:\n                continue\n            # Skip the edge if it forms a cycle.\n            if uf.find_parent(edges[i][0]) == uf.find_parent(edges[i][1]):\n                continue\n            # Union the vertices and add the edge\'s weight to the MST.\n            uf.union(edges[i][0], edges[i][1])\n            weight += edges[i][2]\n        \n        # Check if all vertices are connected (i.e., a valid MST).\n        for i in range(n):\n            if uf.find_parent(i) != uf.find_parent(0):\n                return float(\'inf\')  # Return infinity if the graph is not connected.\n        \n        # Return the total weight of the MST.\n        return weight\n\n```\n```C# []\npublic class Solution {\n    // Class to represent an edge in the graph\n    public class Edge {\n        public int id { get; set; } // Unique identifier for the edge\n        public int from { get; set; } // Start node of the edge\n        public int to { get; set; } // End node of the edge\n        public int cost { get; set; } // Cost or weight of the edge\n    }\n\n    // Disjoint Set Union (DSU) class to support union-find operations for Kruskal\'s algorithm\n    class DSU {\n        int[] par, sz; // Arrays to store parent and size of each component\n        public int componentCount; // Number of connected components\n\n        // Constructor to initialize DSU for \'n\' nodes\n        public DSU(int n) {\n            par = new int[n]; // Initialize the parent array\n            componentCount = n; // Initially, every node is its own component\n            sz = new int[n]; // Initialize size array to 1 for each node\n            for (int i = 0; i < n; i++) {\n                par[i] = i; // Every node is its own parent (self-loop)\n                sz[i] = 1; // Size of each component is 1 initially\n            }\n        }\n\n        // Method to find the parent of node \'u\' with path compression\n        public int FindParent(int u) {\n            if (par[u] == u) return u; // If \'u\' is its own parent, return \'u\'\n            int p = FindParent(par[u]); // Recursively find the parent\n            par[u] = p; // Path compression for efficiency\n            return p;\n        }\n\n        // Method to check if two nodes belong to the same component\n        public bool IsSameComponent(int u, int v) => FindParent(u) == FindParent(v);\n\n        // Method to join two components\n        public void Join(int u, int v) {\n            u = FindParent(u); // Find parent of \'u\'\n            v = FindParent(v); // Find parent of \'v\'\n            if (u == v) return; // If they are already in the same component, do nothing\n            // Union by size: attach the smaller tree under the larger one\n            if (sz[u] < sz[v]) (u, v) = (v, u); \n            par[v] = u; // Make \'u\' the parent of \'v\'\n            sz[u] += sz[v]; // Update the size of the new component\n            componentCount--; // Decrease the component count\n        }\n    }\n\n    // Kruskal\'s algorithm to find Minimum Spanning Tree (MST)\n    // Optionally starts with a specific edge \'taken\'\n    int kruskal(PriorityQueue<Edge, int> edges, int nodes, Edge taken = null) {\n        int res = 0; // Result to store the total cost of the MST\n        DSU dsu = new DSU(nodes); // Initialize DSU for all nodes\n\n        // If a specific edge is already taken, join its nodes and add its cost\n        if (taken != null) {\n            dsu.Join(taken.from, taken.to);\n            res += taken.cost;\n        }\n\n        // While there are still multiple components and edges to process\n        while (dsu.componentCount > 1 && edges.Count > 0) {\n            var e = edges.Dequeue(); // Get the edge with the smallest cost\n            if (dsu.IsSameComponent(e.from, e.to)) continue; // If they are already connected, skip\n            dsu.Join(e.from, e.to); // Join the two components\n            res += e.cost; // Add the edge\'s cost to the result\n        }\n\n        // If not all components are connected, return infinity (not a valid MST)\n        if (dsu.componentCount > 1) return Int32.MaxValue;\n        return res; // Return the total cost of the MST\n    }\n\n    // Method to create a priority queue of edges, with an option to skip a specific edge\n    public PriorityQueue<Edge, int> GetEdges(int[][] edges, int skippedIdx = -1) {\n        PriorityQueue<Edge, int> edgesPq = new(Comparer<int>.Create((a, b) => a.CompareTo(b))); // PriorityQueue by edge cost\n        for (int i = 0; i < edges.Length; i++) {\n            if (i == skippedIdx) continue; // Skip the edge if needed\n            edgesPq.Enqueue(new Edge { id = i, from = edges[i][0], to = edges[i][1], cost = edges[i][2] }, edges[i][2]); // Add edge to queue\n        }\n        return edgesPq; // Return the priority queue\n    }\n\n    // Main method to find critical and pseudo-critical edges in an MST\n    public IList<IList<int>> FindCriticalAndPseudoCriticalEdges(int n, int[][] edges) {\n        int mstCost = kruskal(GetEdges(edges), n); // Find the cost of the MST without skipping any edge\n        List<IList<int>> res = new List<IList<int>>() { new List<int>(), new List<int>() }; // Initialize result lists for critical and pseudo-critical edges\n\n        // Iterate over each edge to classify it\n        for (int i = 0; i < edges.Length; i++) {\n            // Check if skipping the current edge increases the MST cost\n            int curCost = kruskal(GetEdges(edges, i), n);\n            if (curCost > mstCost) res[0].Add(i); // If cost increases, it\'s a critical edge\n            else {\n                // Check if including the current edge still results in the same MST cost\n                Edge taken = new Edge { id = i, from = edges[i][0], to = edges[i][1], cost = edges[i][2] };\n                curCost = kruskal(GetEdges(edges), n, taken);\n                if (curCost == mstCost) res[1].Add(i); // If cost remains the same, it\'s a pseudo-critical edge\n            }\n        }\n\n        return res; // Return the result lists\n    }\n}\n\n```\n```Javascript []\nclass UnionFind {\n    // Constructor initializes the UnionFind data structure for `n` elements.\n    constructor(n) {\n        // Create an array `parents` where each element is its own parent initially.\n        this.parents = [];\n        for (let i = 0; i < n; i++) {\n            this.parents.push(i);\n        }\n        // The count keeps track of the number of connected components.\n        this.count = n;\n    }\n\n    // Find function implements path compression to find the root of the given index.\n    find(index) {\n        // Get the parent of the current index.\n        const parent = this.parents[index];\n        // If the parent is the same as the index, it means we have found the root.\n        if (parent === index) return index;\n\n        // Recursively find the root of the parent and apply path compression.\n        let root = this.find(parent);\n        this.parents[index] = root;\n        return root;\n    }\n\n    // Union function merges two sets represented by index1 and index2.\n    union(index1, index2) {\n        // Find the roots of the two indices.\n        let p1 = this.find(index1);\n        let p2 = this.find(index2);\n\n        // If they have different roots, merge them by updating the parent array.\n        if (p1 !== p2) {\n            this.count--; // Reduce the number of connected components.\n            this.parents[p1] = p2; // Make p2 the parent of p1.\n            return true;\n        }\n\n        // If the roots are the same, they are already connected, so return false.\n        return false;\n    }\n}\n\n// Main function to find critical and pseudo-critical edges in a Minimum Spanning Tree (MST).\nvar findCriticalAndPseudoCriticalEdges = function(n, edges) {\n    let criticalEdges = [], psuedoCriticalEdges = [], map = new Map();\n    \n    // Store the index of each edge in a map for quick lookup later.\n    edges.forEach((edge, i) => map.set(edge, i));\n    \n    // Sort edges based on their weights (third value in each edge).\n    edges.sort((a, b) => a[2] - b[2]);\n    \n    // Helper function to build the MST, optionally forcing an edge to be picked or skipped.\n    const buildMST = (pick, skip) => {\n        let uf = new UnionFind(n), cost = 0;\n        \n        // If a specific edge is picked, add it to the MST first.\n        if (pick !== null) {\n            uf.union(pick[0], pick[1]);\n            cost += pick[2];\n        }\n        \n        // Iterate over all edges and add them to the MST unless the edge is skipped.\n        for (let edge of edges) {\n            if (edge !== skip && uf.union(edge[0], edge[1])) {\n                cost += edge[2];\n            }\n        }\n        \n        // If the entire graph is connected (count == 1), return the total cost, otherwise return a large value.\n        return uf.count === 1 ? cost : Number.MAX_SAFE_INTEGER;\n    };\n    \n    // Calculate the minimum cost of the MST without forcing any edges.\n    const minCost = buildMST(null, null);\n    \n    // Iterate through all edges to determine critical and pseudo-critical edges.\n    for (let edge of edges) {\n        const index = map.get(edge);\n        \n        // First, check if the edge is critical by skipping it and rebuilding the MST.\n        const costWithout = buildMST(null, edge);\n        if (costWithout > minCost) {\n            criticalEdges.push(index); // If skipping the edge increases the cost, it is critical.\n        } else {\n            // If the edge is not critical, check if it is pseudo-critical by forcing it to be in the MST.\n            const costWith = buildMST(edge, null);\n            if (costWith === minCost) psuedoCriticalEdges.push(index);\n        }\n    }\n    \n    // Return the list of critical and pseudo-critical edges.\n    return [criticalEdges, psuedoCriticalEdges];\n};\n\n```\n```Kotlin []\nimport kotlin.math.*\nimport kotlin.comparisons.*\n\nclass Solution {\n\n    // Data class to represent an edge in the graph with nodes, weight, and index.\n    data class Edge(\n        val node1: Int,  // First node of the edge\n        val node2: Int,  // Second node of the edge\n        val weight: Int, // Weight of the edge\n        val number: Int  // Index of the edge in the original input array\n    )\n    \n    // Union-Find (Disjoint Set Union) class to help in checking connectivity\n    class UnionFind(val size: Int) {\n        // Array to store the parent and size of each set (pair of parent node and set size)\n        private val content: Array<Pair<Int, Int>> = Array(size) { it to 1 }\n        \n        // Function to perform union of two sets (merge two sets)\n        fun union(first: Int, second: Int) {\n            // Find the root of both nodes\n            val firstRoot: Pair<Int, Int> = root(first)\n            val secondRoot: Pair<Int, Int> = root(second)\n            \n            // If they are not already connected, merge the sets\n            if (firstRoot.first != secondRoot.first) {\n                // Determine which set is larger to maintain balance\n                var higher: Pair<Int, Int> = maxOf(firstRoot, secondRoot, object: Comparator<Pair<Int, Int>> {\n                    override fun compare(firstPair: Pair<Int, Int>, secondPair: Pair<Int, Int>): Int {\n                        return firstPair.second - secondPair.second // Compare by set size\n                    }\n                })\n                \n                // Update the size of the larger set after merging\n                higher = Pair(higher.first, higher.second + min(firstRoot.second, secondRoot.second))\n                \n                // Update the parent pointer for both sets\n                content[firstRoot.first] = higher\n                content[secondRoot.first] = higher\n            }\n        }\n        \n        // Function to check if two nodes are in the same set\n        fun connected(first: Int, second: Int): Boolean {\n            return root(first).first == root(second).first\n        }\n        \n        // Function to find the root of a node with path compression optimization\n        fun root(node: Int): Pair<Int, Int> {\n            var cur = node\n            \n            // Path compression: update parent pointers along the path\n            while (content[cur].first != cur) {\n                content[cur] = content[content[cur].first] // Move up to the parent\n                cur = content[cur].first // Continue to the root\n            }\n            \n            return content[cur] // Return the root and size\n        }\n    }\n    \n    // Main function to find critical and pseudo-critical edges in a minimum spanning tree (MST)\n    fun findCriticalAndPseudoCriticalEdges(n: Int, edges: Array<IntArray>): List<List<Int>> {\n        val critical: MutableList<Int> = mutableListOf() // List of critical edges\n        val pseudo: MutableList<Int> = mutableListOf()   // List of pseudo-critical edges\n        \n        // Convert input edges to a list of Edge objects and sort by weight\n        val sortedEdges = edges.asSequence()\n            .mapIndexed { index, edge -> \n                Edge(edge[0], edge[1], edge[2], index) \n            }\n            .sortedBy { it.weight } // Sort edges by weight for Kruskal\'s algorithm\n            .toList()\n        \n        // Calculate the weight of the minimum spanning tree (MST) without any edge being blocked\n        val minWeight = findMSTWeight(n, sortedEdges)\n        \n        // Iterate through each edge to determine if it is critical or pseudo-critical\n        for (edge in sortedEdges) {   \n            // If blocking the edge increases the MST weight, it is a critical edge\n            if (findMSTWeight(n, sortedEdges, blocked = edge) != minWeight) {\n                critical.add(edge.number)\n            } \n            // If forcing the edge into the MST gives the same weight as the original MST, it is a pseudo-critical edge\n            else if (findMSTWeight(n, sortedEdges, peeked = edge) == minWeight) {\n                pseudo.add(edge.number)\n            }\n        }\n        \n        return listOf(critical, pseudo) // Return the lists of critical and pseudo-critical edges\n    }\n    \n    // Helper function to find the weight of the minimum spanning tree (MST)\n    // Optionally, a specific edge can be blocked or forced into the MST\n    fun findMSTWeight(n: Int, edges: List<Edge>, blocked: Edge? = null, peeked: Edge? = null): Int {\n        val union = UnionFind(n) // Initialize the union-find data structure\n        var weight = 0 // Initialize the total weight of the MST\n        \n        // If a specific edge is forced into the MST, add it first\n        peeked?.let { \n            union.union(it.node1, it.node2) // Union the nodes of the edge\n            weight += it.weight // Add the weight of the edge to the MST\n        }\n        \n        // Process the edges, skipping the blocked edge and adding other edges if they connect different components\n        for (edge in edges) {\n            if (blocked?.number != edge.number && !union.connected(edge.node1, edge.node2)) {\n                union.union(edge.node1, edge.node2) // Union the nodes of the edge\n                weight += edge.weight // Add the weight of the edge to the MST\n            }\n        }\n        \n        return weight // Return the total weight of the MST\n    }\n}\n\n```\n\n\n---\n![download.jpg](https://assets.leetcode.com/users/images/5196fec2-1dd4-4b82-9700-36c5a0e72623_1692159956.9446952.jpeg)\n\n---
['Union Find', 'Sorting', 'Python', 'C++', 'Java', 'TypeScript', 'Python3', 'Kotlin', 'JavaScript', 'C#']