C# Solution for Find Critical And Pseudo Critical Edges in Minimum Spanning Tree Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem revolves around identifying critical and pseudo-critical edges in a minimum
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem revolves around identifying critical and pseudo-critical edges in a minimum spanning tree (MST) of a weighted undirected graph. A critical edge is one whose removal would cause the MST weight to increase, and a pseudo-critical edge is one that can appear in some MSTs but not all.\n\nThe main idea is to iterate through all edges in ascending order of weights, consider each edge\'s impact on the MST, and identify if it\'s critical or pseudo-critical.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Initial Preparation: First, the input edges are modified to include their indices for identification purposes. Then, they are sorted based on their weights in ascending order.\n\n1. MST Calculation: The MSTWeight function calculates the weight of the MST while considering optional skipIndex (an edge to skip) and addIndex (an edge to include). This function uses the Union-Find (Disjoint Set Union) data structure to efficiently determine the MST\'s weight.\n\n1. Identifying Critical and Pseudo-Critical Edges: Iterate through each edge, and:\n\n- Calculate the MST weight without considering the current edge (skipIndex).\n- If the MST weight changes, the current edge is critical.\n- Calculate the MST weight by including only the current edge (addIndex).\n- If the MST weight remains the same as the original, the edge is pseudo-critical.\n4. Returning Results: The indices of critical and pseudo-critical edges are collected in separate lists, which are returned as the final output.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- Sorting the edges initially takes O(m * log m) time.\n- Each iteration over the edges takes O(m) time.\n- Calculating the MST weight for each edge (worst case) takes O(n * alpha(n)) time (amortized constant time for Union-Find operations).\n- The overall time complexity is dominated by the sorting step, resulting in O(m * log m), where m is the number of edges.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n- The space complexity of the input edges array is O(m).\n- The Union-Find data structure uses O(n) space.\n- The space complexity is dominated by the input edges array, resulting in O(m).\n\n# Code\n```\npublic class Solution {\n    public IList<IList<int>> FindCriticalAndPseudoCriticalEdges(int n, int[][] edges) {\n        int m = edges.Length;\n        for (int i = 0; i < m; i++) {\n            edges[i] = new int[] { edges[i][0], edges[i][1], edges[i][2], i };\n        }\n        \n        Array.Sort(edges, (a, b) => a[2] - b[2]);\n        \n        int mstWeight = MSTWeight(n, edges, -1, -1);\n        \n        List<int> criticalEdges = new List<int>();\n        List<int> pseudoCriticalEdges = new List<int>();\n        \n        for (int i = 0; i < m; i++) {\n            if (mstWeight != MSTWeight(n, edges, i, -1)) {\n                criticalEdges.Add(edges[i][3]);\n            } else if (mstWeight == MSTWeight(n, edges, -1, i)) {\n                pseudoCriticalEdges.Add(edges[i][3]);\n            }\n        }\n        \n        return new List<IList<int>> { criticalEdges, pseudoCriticalEdges };\n    }\n    \n    private int MSTWeight(int n, int[][] edges, int skipIndex, int addIndex) {\n        int weight = 0;\n        UnionFind uf = new UnionFind(n);\n        \n        if (addIndex != -1) {\n            uf.Union(edges[addIndex][0], edges[addIndex][1]);\n            weight += edges[addIndex][2];\n        }\n        \n        for (int i = 0; i < edges.Length; i++) {\n            if (i == skipIndex || i == addIndex) continue;\n            if (uf.Union(edges[i][0], edges[i][1])) {\n                weight += edges[i][2];\n            }\n        }\n        \n        return uf.Count == 1 ? weight : int.MaxValue;\n    }\n}\n\npublic class UnionFind {\n    private int[] parent;\n    private int[] rank;\n    public int Count { get; private set; }\n    \n    public UnionFind(int size) {\n        parent = new int[size];\n        rank = new int[size];\n        Count = size;\n        for (int i = 0; i < size; i++) {\n            parent[i] = i;\n            rank[i] = 1;\n        }\n    }\n    \n    public int Find(int x) {\n        if (parent[x] != x) {\n            parent[x] = Find(parent[x]);\n        }\n        return parent[x];\n    }\n    \n    public bool Union(int x, int y) {\n        int rootX = Find(x);\n        int rootY = Find(y);\n        \n        if (rootX == rootY) {\n            return false;\n        }\n        \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        Count--;\n        return true;\n    }\n}\n\n```
['C#']