💥Runtime beats 92.86%, Memory beats 100.00% [EXPLAINED]
Intuition\nThe intuition behind the problem is to identify edges in a graph that are essential for maintaining the minimum spanning tree (MST) structure. Critic
# Intuition\nThe intuition behind the problem is to identify edges in a graph that are essential for maintaining the minimum spanning tree (MST) structure. Critical edges are those whose removal increases the total weight of the MST, while pseudo-critical edges can be included in some MSTs but not all.\n\n# Approach\nThe approach is to sort the edges by weight, use Kruskal\'s algorithm to find the MST while tracking the total weight, then check each edge: first to see if it is critical by attempting to construct the MST without it, and second to see if it is pseudo-critical by forcing it into the MST and checking if we can still form a valid tree.\n\n# Complexity\n- Time complexity:\nO(ElogE) for sorting the edges and O(E\u22C5\u03B1(N)) for the union-find operations, where E is the number of edges and N is the number of nodes.\n\n- Space complexity:\nO(N+E) for storing the parent and rank arrays used in the union-find structure and the edges themselves.\n\n# Code\n```csharp []\npublic class Solution {\n    public IList<IList<int>> FindCriticalAndPseudoCriticalEdges(int n, int[][] edges) {\n        // Step 1: Prepare edges with their original indices\n        for (int i = 0; i < edges.Length; i++) {\n            edges[i] = new int[] { edges[i][0], edges[i][1], edges[i][2], i };\n        }\n        \n        // Step 2: Sort edges by weight\n        Array.Sort(edges, (a, b) => a[2].CompareTo(b[2]));\n\n        // Step 3: Find the MST weight\n        int mstWeight = Kruskal(n, edges, null, null);\n        \n        IList<int> critical = new List<int>();\n        IList<int> pseudoCritical = new List<int>();\n        \n        // Step 4: Check for critical and pseudo-critical edges\n        for (int i = 0; i < edges.Length; i++) {\n            // Check if edge i is critical\n            if (Kruskal(n, edges, edges[i], null) > mstWeight) {\n                critical.Add(edges[i][3]);\n            } else if (Kruskal(n, edges, null, edges[i]) == mstWeight) {\n                // Check if edge i is pseudo-critical\n                pseudoCritical.Add(edges[i][3]);\n            }\n        }\n        \n        return new List<IList<int>> { critical, pseudoCritical };\n    }\n\n    private int Kruskal(int n, int[][] edges, int[] skipEdge, int[] forceEdge) {\n        int[] parent = new int[n];\n        int[] rank = new int[n];\n        for (int i = 0; i < n; i++) {\n            parent[i] = i;\n            rank[i] = 0;\n        }\n\n        int Find(int x) {\n            if (parent[x] != x) {\n                parent[x] = Find(parent[x]);\n            }\n            return parent[x];\n        }\n\n        void Union(int x, int y) {\n            int rootX = Find(x);\n            int rootY = Find(y);\n            if (rootX != rootY) {\n                if (rank[rootX] > rank[rootY]) {\n                    parent[rootY] = rootX;\n                } else if (rank[rootX] < rank[rootY]) {\n                    parent[rootX] = rootY;\n                } else {\n                    parent[rootY] = rootX;\n                    rank[rootX]++;\n                }\n            }\n        }\n\n        int totalWeight = 0;\n        int edgesUsed = 0;\n\n        // If there\'s a forced edge, include it\n        if (forceEdge != null) {\n            totalWeight += forceEdge[2];\n            Union(forceEdge[0], forceEdge[1]);\n            edgesUsed++;\n        }\n\n        // Iterate through edges and apply union-find\n        for (int i = 0; i < edges.Length; i++) {\n            if (edges[i] == skipEdge) continue; // Skip the edge if it\'s the one to be skipped\n            int u = edges[i][0], v = edges[i][1], weight = edges[i][2];\n\n            if (Find(u) != Find(v)) {\n                Union(u, v);\n                totalWeight += weight;\n                edgesUsed++;\n            }\n        }\n\n        // Check if all vertices are connected\n        return edgesUsed == n - 1 ? totalWeight : int.MaxValue;\n    }\n}\n\n```
['C#']