Sponsored
Sponsored
This approach utilizes the Union-Find (or Disjoint Set Union, DSU) data structure to manage the connectivity of nodes. The critical idea is to process edge types in a specific order to ensure that both Alice and Bob can fully traverse the graph while maximizing the number of removable edges:
Time Complexity: O(E * α(n)), where E is the number of edges and α(n) is the inverse Ackermann function, effectively constant.
Space Complexity: O(n) for storing the disjoint sets for both Alice and Bob.
1#include <vector>
2#include <numeric>
3
4class DSU {
5public:
6 std::vector<int> parent, rank;
7 DSU(int n) : parent(n), rank(n, 1) {
8 std::iota(parent.begin(), parent.end(), 0);
9 }
10 int find(int x) {
11 if (x != parent[x]) {
12 parent[x] = find(parent[x]);
}
return parent[x];
}
bool unite(int x, int y) {
int rootX = find(x), rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
return true;
}
return false;
}
};
int maxNumEdgesToRemove(int n, std::vector<std::vector<int>>& edges) {
DSU dsuAlice(n), dsuBob(n);
int savedEdges = 0, types = 0;
for (const auto& edge : edges) {
if (edge[0] == 3) {
bool unitedAlice = dsuAlice.unite(edge[1] - 1, edge[2] - 1);
bool unitedBob = dsuBob.unite(edge[1] - 1, edge[2] - 1);
if (unitedAlice) {
types++;
} else {
savedEdges++;
}
}
}
DSU dsuCopyAlice = dsuAlice, dsuCopyBob = dsuBob;
for (const auto& edge : edges) {
if (edge[0] == 1) {
if (dsuAlice.unite(edge[1] - 1, edge[2] - 1)) {
types++;
} else {
savedEdges++;
}
}
if (edge[0] == 2) {
if (dsuBob.unite(edge[1] - 1, edge[2] - 1)) {
types++;
} else {
savedEdges++;
}
}
}
if (types != (n - 1) * 2) return -1;
return savedEdges;
}
The solution involves defining a DSU class to handle node connectivity tasks with methods for finding roots and uniting sets. The maxNumEdgesToRemove function initializes two DSUs (one each for Alice and Bob) and processes the edges: prioritizing type 3 edges and using them for both Alice and Bob, while keeping track of redundant edges.
If type 3 edges do not contribute to further connectivity, they are considered removable. After confirming that both Alice’s and Bob’s graphs are fully connected (i.e., types value matches expected connections with no isolated components), the number of potentially removable edges is returned; otherwise, it outputs -1.