[Java] Variant of finding MST with explanation
This question is similar to find MST. But we need some tricks to verify whether an edge \n\n1) belongs to at least one MST.\n2) belongs to every MST.\n\nTo chec
This question is similar to find MST. But we need some tricks to verify whether an edge \n\n1) belongs to at least one MST.\n2) belongs to every MST.\n\nTo check 1), we enforce the MST generating process to include current edge and see whether it has the same value as our MST.\n\nTo check 2), we exclude current edge from MST generating process and see whether MST can be obtained.\n\n**Solution1**\nNumber of edges is at most N^2. For each edge, we need to find the MST, which takes O(N^2 logN). So total time complexity is O(N^4 logN)\n\n```\nclass Solution {\n    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {\n        List<List<Integer>> result = new ArrayList<>();\n        List<Integer> criq = new ArrayList<>();\n        List<Integer> pseu_criq = new ArrayList<>();\n        \n        int mst = MST(Integer.MAX_VALUE, Integer.MAX_VALUE, edges, n);\n        \n        for (int i = 0; i < edges.length; i ++) {\n            int notInclude = MST(Integer.MAX_VALUE, i, edges, n);\n            int mustInclude = MST(i, Integer.MAX_VALUE, edges, n);\n            \n            if (notInclude > mst || notInclude == -1) {\n                criq.add(i);\n            } else if (mustInclude == mst) {\n                pseu_criq.add(i);\n            }\n        }\n        \n        result.add(criq);\n        result.add(pseu_criq);\n        \n        return result;\n    }\n    \n    private int find(int node, int[] parent) {\n        if (node == parent[node]) {\n            return node;\n        }\n        parent[node] = find(parent[node], parent);\n        return parent[node];\n    }\n    \n    private int MST(int mustIncludeEdge, int NotIncludeEdge, int[][] edges, int n) {\n        int result = 0;\n        int[] parent = new int[n];\n        for (int i = 0; i < n; i ++) {\n            parent[i] = i;\n        }\n        \n        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[2] - b[2]));\n        \n        for (int i = 0; i < edges.length; i ++) {\n            if (i != NotIncludeEdge) {\n                pq.offer(edges[i]);\n            }\n        }\n        \n        if (mustIncludeEdge != Integer.MAX_VALUE) {\n            int start = edges[mustIncludeEdge][0];\n            int end = edges[mustIncludeEdge][1];\n            int ps = find(start, parent), pe = find(end, parent);\n            result += edges[mustIncludeEdge][2];\n            parent[ps] = pe;\n        }\n        \n        while (!pq.isEmpty()) {\n            int[] edge = pq.poll();\n            int pa = find(edge[0], parent), pb = find(edge[1], parent);\n            if (pa == pb) {\n                continue;\n            }\n            \n            result += edge[2];\n            parent[pa] = pb;\n        }\n        \n        // Detect whether graph is connected\n        for (int i = 1; i < n; i ++) {\n            if (find(i - 1, parent) != find(i, parent)) {\n                return -1;\n            }\n        }\n        \n        return result;\n    }\n}\n```\n\n\n**Solution2: Improve time complexity to O(E^2 + ElogE) by sorting edges first**\n```\nclass Solution {\n    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {\n        List<List<Integer>> result = new ArrayList<>();\n        List<Integer> criq = new ArrayList<>();\n        List<Integer> pseu_criq = new ArrayList<>();\n        Map<int[], Integer> map = new HashMap<>();\n        for (int i = 0; i < edges.length; i ++) { //memorize original index of edges\n            map.put(edges[i], i); \n        }\n        Arrays.sort(edges, (a, b) -> (a[2] - b[2]));\n        int mst = MST(Integer.MAX_VALUE, Integer.MAX_VALUE, edges, n);\n        \n        for (int i = 0; i < edges.length; i ++) {\n            int notInclude = MST(Integer.MAX_VALUE, i, edges, n);\n            int mustInclude = MST(i, Integer.MAX_VALUE, edges, n);\n            \n            if (notInclude > mst || notInclude == -1) {\n                criq.add(map.get(edges[i]));\n            } else if (mustInclude == mst) {\n                pseu_criq.add(map.get(edges[i]));\n            }\n        }\n        \n        result.add(criq);\n        result.add(pseu_criq);\n        \n        return result;\n    }\n    \n    private int find(int node, int[] parent) {\n        if (node == parent[node]) {\n            return node;\n        }\n        parent[node] = find(parent[node], parent);\n        return parent[node];\n    }\n    \n    private int MST(int mustIncludeEdge, int NotIncludeEdge, int[][] edges, int n) {\n        int result = 0;\n        int[] parent = new int[n];\n        for (int i = 0; i < n; i ++) {\n            parent[i] = i;\n        }\n        \n        if (mustIncludeEdge != Integer.MAX_VALUE) {\n            int start = edges[mustIncludeEdge][0];\n            int end = edges[mustIncludeEdge][1];\n            int ps = find(start, parent), pe = find(end, parent);\n            result += edges[mustIncludeEdge][2];\n            parent[ps] = pe;\n        }\n        \n        for (int i = 0; i < edges.length; i ++) {\n            if (i == mustIncludeEdge || i == NotIncludeEdge) {\n                continue;\n            }\n            int start = edges[i][0], end = edges[i][1], weight = edges[i][2];\n            int ps = find(start, parent), pe = find(end, parent);\n            if (ps != pe) {\n                result += weight;\n                parent[ps] = pe;\n            }\n        }\n        \n        // Detect whether graph is connected\n        for (int i = 1; i < n; i ++) {\n            if (find(i - 1, parent) != find(i, parent)) {\n                return -1;\n            }\n        }\n        return result;\n    }\n}\n```
[]