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 <stdio.h>
2#include <stdlib.h>
3
4struct DSU {
5 int *parent, *
This code defines a struct DSU representing the Disjoint-Set Union data structure for managing connected components. The functions createDSU, find, and unionSet handle initialization, set finding, and union operations, respectively.
The main function, maxNumEdgesToRemove, processes the edges by type. Type 3 edges are processed first because they serve both Alice and Bob. Then type 1 and 2 edges are processed separately for Alice’s and Bob’s connectivity. The variable savedEdges stores the number of redundant edges found. After processing, checking the number of connected components in alice and bob determines if the graph is fully traversable, and returns the maximum number of removable edges.