Sponsored
Sponsored
This approach involves using Kruskal's algorithm to find the Minimum Spanning Tree. First, sort all edges by weight. Then, use a Union-Find data structure to maintain and check connectivity of the nodes as edges are added to the MST. Critical edges are those whose exclusion from the MST will increase its total weight, whereas pseudo-critical edges are those that can be in any MST when forced to be present.
The time complexity is O(E log E), where E is the number of edges, mainly due to sorting edges. Space complexity is O(V), where V is the number of vertices, due to the Union-Find structure.
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class UnionFind {
6public:
7 vector<int> parent, rank;
8 UnionFind(int size) : parent(size), rank(size, 1) {
9 for (int i = 0; i < size; ++i) {
10 parent[i] = i;
11 }
12 }
13 int find(int u) {
14 if (parent[u] != u) parent[u] = find(parent[u]);
15 return parent[u];
16 }
17 bool union_sets(int u, int v) {
18 int rootU = find(u);
19 int rootV = find(v);
20 if (rootU != rootV) {
21 if (rank[rootU] > rank[rootV])
22 parent[rootV] = rootU;
23 else if (rank[rootU] < rank[rootV])
24 parent[rootU] = rootV;
25 else {
26 parent[rootV] = rootU;
27 rank[rootU]++;
28 }
29 return true;
30 }
31 return false;
32 }
33};
34
35class Solution {
36public:
37 vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
38 int m = edges.size();
39 vector<vector<int>> edgesWithIndex;
40 for (int i = 0; i < m; ++i) {
41 edgesWithIndex.push_back({edges[i][2], edges[i][0], edges[i][1], i});
42 }
43 sort(edgesWithIndex.begin(), edgesWithIndex.end());
44
45 auto kruskal = [&](int include = -1, int exclude = -1) -> int {
46 UnionFind uf(n);
47 int weight = 0;
48 int edges_used = 0;
49 if (include != -1) {
50 auto &[w, u, v, idx] = edgesWithIndex[include];
51 if (uf.union_sets(u, v)) {
52 weight += w;
53 edges_used++;
54 }
55 }
56 for (int i = 0; i < m; ++i) {
57 if (i == exclude) continue;
58 auto &[w, u, v, idx] = edgesWithIndex[i];
59 if (uf.union_sets(u, v)) {
60 weight += w;
61 edges_used++;
62 }
63 if (edges_used == n - 1) break;
64 }
65 return (edges_used == n - 1) ? weight : INT_MAX;
66 };
67
68 int mst_weight = kruskal();
69 vector<int> critical, pseudo_critical;
70 for (int i = 0; i < m; ++i) {
71 if (kruskal(-1, i) > mst_weight) {
72 critical.push_back(edgesWithIndex[i][3]);
73 } else if (kruskal(i) == mst_weight) {
74 pseudo_critical.push_back(edgesWithIndex[i][3]);
75 }
76 }
77 return {critical, pseudo_critical};
78 }
79};Using the concept of Kruskal's algorithm, this C++ solution sorts edges based on weights and applies a Union-Find structure to determine MST connectivity by iterating through edges and uniting components. Critical edges are assessed by omitting them and checking if the exclusion increases the MST weight, whereas pseudo-critical edges are checked by forcing their inclusion.
This approach leverages Kruskal's algorithm to build MSTs while testing each edge's criticality and pseudo-criticality. We initially use Kruskal's algorithm to determine the MST and its weight without any edge removal. We then experiment with excluding and mandatorily including each edge to ascertain its nature: critical or pseudo-critical.
Steps:
Time Complexity: O(E^2 * log(E)) where E is the number of edges, due to sorting and constructing MST for each edge.
Space Complexity: O(E + V) where E is the number of edges and V is the number of vertices used for storing edges and union-find data structure.
1class
This approach focuses on constructing subsets of edges that definitely belong or don't belong in the MST. By manipulating combinations of edges and recalculating the MST weight, this approach checks the necessity of each edge.
Steps:
Time Complexity: O(E^2 * log(E)) due to sorting edges and iterating for each edge's condition.
Space Complexity: O(E + V) for storing edges and union-find structure during operations.
1#include <vector>
2#include <algorithm>
3
class UnionFind {
public:
std::vector<int> parent, rank;
UnionFind(int n) : parent(n), rank(n, 0) {
for (int i = 0; i < n; ++i) parent[i] = i;
}
int find(int u) {
if (parent[u] != u) parent[u] = find(parent[u]);
return parent[u];
}
bool unionSets(int u, int v) {
int rootU = find(u), rootV = find(v);
if (rootU != rootV) {
if (rank[rootU] > rank[rootV])
parent[rootV] = rootU;
else if (rank[rootU] < rank[rootV])
parent[rootU] = rootV;
else {
parent[rootV] = rootU;
rank[rootU]++;
}
return true;
}
return false;
}
};
class Solution {
public:
std::vector<std::vector<int>> findCriticalAndPseudoCriticalEdges(int n, std::vector<std::vector<int>>& edges) {
std::vector<std::tuple<int, int, int, int>> indexedEdges;
for (int i = 0; i < edges.size(); ++i) {
indexedEdges.emplace_back(edges[i][0], edges[i][1], edges[i][2], i);
}
std::sort(indexedEdges.begin(), indexedEdges.end(), [](auto& e1, auto& e2) {
return std::get<2>(e1) < std::get<2>(e2);
});
auto kruskal = [&](int excludeEdge, int forceEdge) {
UnionFind uf(n);
int totalWeight = 0, edgesUsed = 0;
if (forceEdge != -1) {
auto [u, v, w, idx] = indexedEdges[forceEdge];
if (uf.unionSets(u, v)) {
totalWeight += w;
edgesUsed++;
}
}
for (auto& [u, v, w, idx] : indexedEdges) {
if (idx != excludeEdge && uf.unionSets(u, v)) {
totalWeight += w;
edgesUsed++;
}
}
return (edgesUsed == n - 1) ? totalWeight : INT_MAX;
};
int mstWeight = kruskal(-1, -1);
std::vector<int> critical, pseudo_critical;
for (int i = 0; i < edges.size(); ++i) {
if (kruskal(i, -1) > mstWeight) {
critical.push_back(i);
} else if (kruskal(-1, i) == mstWeight) {
pseudo_critical.push_back(i);
}
}
return {critical, pseudo_critical};
}
};This JavaScript solution defines a Union-Find class for performing union and find operations, essential for Kruskal's algorithm. Two checks are performed for each edge: one to ascertain if its exclusion raises the MST weight (indicative of criticality), and another to observe if a forced inclusion keeps the MST weight constant (demonstrating pseudo-criticality). Each of these operations helps distinguish between critical and pseudo-critical edges effectively.
This C++ solution effectively uses the Union-Find data structure for Kruskal's algorithm to determine edge connectivity. It manages edge inclusion/exclusion flexibly, ensuring optimal MST weights are computed to ascertain the critical or pseudo-critical nature of edges. Comparison of MST weight with and without specific edges indicates their status. This solution demonstrates high proficiency in handling complex graph structures using classical algorithms.