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.
1class DSU {
2 constructor(n) {
3 this.parent = Array.from({ length: n },
The JavaScript version employs a class DSU
to manage node connectivity using union-find principles. The function maxNumEdgesToRemove
processes the input edge array in stages.
Initially, shared edges (type 3) are prioritized for connectivity with other types handled subsequently for each graph's completeness. A set is used to verify the number of distinct components each DSU represents; ideally, this should output just one, indicative of a fully connected graph.
The graph is traversed, counting redundant (unnecessary) edges, returning this count unless incomplete connectivity is found, where it returns -1
.