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.
1using System;
2using System.Collections.Generic;
3
4public class DSU {
5 private int[] parent, rank;
6 public DSU(int n) {
7 parent = new int[n];
8 rank = new int[n];
9 for (int i = 0; i < n; i++) {
10 parent[i] = i;
11 rank[i] = 1;
12 }
}
public int Find(int x) {
if (x != parent[x]) {
parent[x] = Find(parent[x]);
}
return parent[x];
}
public bool Union(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;
}
}
public class Solution {
public int MaxNumEdgesToRemove(int n, int[][] edges) {
DSU dsuAlice = new DSU(n);
DSU dsuBob = new DSU(n);
int savedEdges = 0;
foreach (var edge in edges) {
if (edge[0] == 3) {
bool unitedAlice = dsuAlice.Union(edge[1] - 1, edge[2] - 1);
bool unitedBob = dsuBob.Union(edge[1] - 1, edge[2] - 1);
if (!unitedAlice || !unitedBob) {
savedEdges++;
}
}
}
foreach (var edge in edges) {
if (edge[0] == 1) {
if (!dsuAlice.Union(edge[1] - 1, edge[2] - 1)) {
savedEdges++;
}
}
if (edge[0] == 2) {
if (!dsuBob.Union(edge[1] - 1, edge[2] - 1)) {
savedEdges++;
}
}
}
int componentsA = 0, componentsB = 0;
for (int i = 0; i < n; i++) {
if (dsuAlice.Find(i) == i) componentsA++;
if (dsuBob.Find(i) == i) componentsB++;
}
return (componentsA == 1 && componentsB == 1) ? savedEdges : -1;
}
}
This C# implementation features a class DSU for managing disjoint sets through path compression and rank management. The MaxNumEdgesToRemove method processes each edge by priority: type 3 edges ensure shared connectivity, while types 1 and 2 enhance Alice's and Bob's paths separately.
It seeks to manage and count redundant edges, checking that both individual's graphs end as fully connected components. If both have more than one component in the end, connectivity is incomplete and -1 is returned, otherwise the function returns the count of removable edges.