1579. Remove Max Number of Edges to Keep Graph Fully Traversable

Intuition

The problem involves determining the maximum number of edges that can be removed while maintaining connectivity between all nodes in an undirected graph for both Alice and Bob. Different edge types restrict traversal permissions to Alice, Bob, or both.

Approach

1. Union-Find Data Structure: - Use a Union-Find (Disjoint Set Union, DSU) data structure to manage connected components for Alice and Bob separately. - Each component in the Union-Find represents a set of nodes that are connected.
2. Edge Classification: - Classify edges into three types based on their traversal permissions (Type 1 for Alice, Type 2 for Bob, Type 3 for both).
3. Union Operations: - Perform union operations in the Union-Find data structure based on edge types: - For Type 3 edges, union nodes for both Alice and Bob. - For Type 1 and Type 2 edges, union nodes only for Alice or Bob respectively.
4. Count Operations: - Count the number of edges removed while performing union operations. This count helps in determining the maximum removable edges.
5. Validation: - After processing all edges, check if both Alice and Bob have exactly one connected component each (i.e., groups == 1 in Union-Find for both).
6. Result Calculation: - If both Alice and Bob have exactly one connected component each, calculate and return the maximum removable edges as total_edges - count. - If either Alice or Bob has more than one connected component (groups > 1), return -1 indicating the graph cannot be fully traversed by both after removing edges.

Complexity

• Time Complexity: O(E * α(V)), where E is the number of edges and α is the inverse Ackermann function (nearly constant time for practical purposes in Union-Find).
• Space Complexity: O(V), where V is the number of nodes, primarily for storing parent pointers and sizes in Union-Find.

Code Explanation

Union-Find Data Structure Initialization

class UnionFind {
    constructor(n) {
        this.parent = new Array(n).fill().map((_, i) => i);
        this.groups = n;
    }

• UnionFind Class Initialization: - constructor(n): Initializes the Union-Find data structure with n nodes. - this.parent: An array where this.parent[i] points to the parent of node i. Initially, each node is its own parent. - this.groups: Keeps track of the number of connected components, initialized to n because initially, each node is its own component.

Find Operation with Path Compression

    find(i) {
        if (this.parent[i] !== i) {
            this.parent[i] = this.find(this.parent[i]);
        }
        return this.parent[i];
    }

• Find Operation (find(i)): - Finds the root (or representative) of the set containing node i. - Uses path compression: When finding the root of i, all nodes along the path are connected directly to the root to flatten the structure, optimizing future queries.

Union Operation for Merging Sets

    union(i, j) {
        const rootI = this.find(i);
        const rootJ = this.find(j);

        if (rootI !== rootJ) {
            this.parent[rootJ] = rootI;
            this.groups--;
            return true;
        }
        return false;
    }
}

• Union Operation (union(i, j)): - Unites the sets containing nodes i and j. - Finds the roots of i and j (rootI and rootJ). - If rootI and rootJ are different (indicating i and j are in different sets), rootJ is made a child of rootI (this.parent[rootJ] = rootI), effectively merging the sets. - Decreases the groups count as the number of connected components decreases by one after a successful union. - Returns true if i and j were in different sets and were successfully united; otherwise, returns false.

Main Function: `maxNumEdgesToRemove` Initialization

/**
 * @param {number} n
 * @param {number[][]} edges
 * @returns {number}
 */
var maxNumEdgesToRemove = function (n, edges) {
    const alice = new UnionFind(n);
    const bob = new UnionFind(n);
    let count = 0;

• Initialization: - alice and bob are instances of the UnionFind class, initialized with n nodes each. These will track connectivity for edges that Alice and Bob can respectively traverse. - count initialized to 0 will track the number of edges that can be removed.

Processing Type 3 Edges

for (let [type, u, v] of edges) {
  if (type === 3 && alice.union(u, v) && bob.union(u, v)) {
    count++;
  }
}

• First Pass: Type 3 Edges: - Loop through all edges (edges array). - For each edge [type, u, v]: - Check if it's a type 3 edge (traversable by both Alice and Bob). - Attempt to union nodes u and v in both alice and bob. - If both alice.union(u, v) and bob.union(u, v) return true (indicating successful unions), increment the count variable to track removable edges.

Processing Type 1 and Type 2 Edges

for (let [type, u, v] of edges) {
  if ((type === 1 && alice.union(u, v)) || (type === 2 && bob.union(u, v))) {
    count++;
  }
}

• Second Pass: Type 1 and Type 2 Edges: - Loop through all edges (edges array) again. - For each edge [type, u, v]: - Check if it's a type 1 edge (Alice-only) or type 2 edge (Bob-only). - Attempt to union nodes u and v in alice for type 1 and in bob for type 2. - If either alice.union(u, v) or bob.union(u, v) returns true, increment the count variable to track removable edges.

Result Evaluation

    if (alice.groups === 1 && bob.groups === 1) {
        return edges.length - count;
    } else {
        return -1;
    }
};

• Result Evaluation: - After processing all edges, check if both Alice (alice.groups === 1) and Bob (bob.groups === 1) can fully traverse the graph. - If both conditions are true, return edges.length - count, which gives the maximum number of removable edges while ensuring the graph remains fully traversable by both. - If either Alice or Bob cannot fully traverse the graph (i.e., more than one connected component for either), return -1 indicating it's impossible for both to traverse the graph fully even after removing edges.

Code

C++

class UnionFind {
public:
    vector parent;
    int groups;

    UnionFind(int n) : parent(n), groups(n - 1) {
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    int find(int i) {
        if (parent[i] != i) {
            parent[i] = find(parent[i]);
        }
        return parent[i];
    }

    bool unionSets(int i, int j) {
        int x = find(i);
        int y = find(j);
        if (x == y) {
            return false;
        } else {
            parent[y] = x;
            --groups;
            return true;
        }
    }
};

class Solution {
public:
    int maxNumEdgesToRemove(int n, vector>& edges) {
        UnionFind alice(n), bob(n);
        int count = 0;

        for (const auto& edge : edges) {
            int type = edge[0], u = edge[1] - 1, v = edge[2] - 1;
            if (type == 3 && alice.unionSets(u, v) && bob.unionSets(u, v)) {
                ++count;
            }
        }
        for (const auto& edge : edges) {
            int type = edge[0], u = edge[1] - 1, v = edge[2] - 1;
            if ((type == 1 && alice.unionSets(u, v)) || (type == 2 && bob.unionSets(u, v))) {
                ++count;
            }
        }

        if (alice.groups == 0 && bob.groups == 0) {
            return edges.size() - count;
        } else {
            return -1;
        }
    }
};

Python

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.groups = n - 1
        
    def find(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]
    
    def union(self, i, j):
        x = self.find(i)
        y = self.find(j)
        if x == y:
            return False
        else:
            self.parent[y] = x
            self.groups -= 1
            return True

class Solution:
    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
        alice = UnionFind(n)
        bob = UnionFind(n)
        count = 0
        
        for edge in edges:
            type, u, v = edge[0], edge[1] - 1, edge[2] - 1
            if type == 3 and alice.union(u, v) and bob.union(u, v):
                count += 1
        
        for edge in edges:
            type, u, v = edge[0], edge[1] - 1, edge[2] - 1
            if (type == 1 and alice.union(u, v)) or (type == 2 and bob.union(u, v)):
                count += 1
        
        if alice.groups == 0 and bob.groups == 0:
            return len(edges) - count
        else:
            return -1

Java

class UnionFind {
    int[] parent;
    int groups;

    UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
        groups = n - 1;
    }

    int find(int i) {
        if (parent[i] != i) {
            parent[i] = find(parent[i]);
        }
        return parent[i];
    }

    boolean union(int i, int j) {
        int x = find(i);
        int y = find(j);
        if (x == y) {
            return false;
        } else {
            parent[y] = x;
            groups--;
            return true;
        }
    }
}

class Solution {
    public int maxNumEdgesToRemove(int n, int[][] edges) {
        UnionFind alice = new UnionFind(n);
        UnionFind bob = new UnionFind(n);
        int count = 0;

        for (int[] edge : edges) {
            int type = edge[0], u = edge[1] - 1, v = edge[2] - 1;
            if (type == 3 && alice.union(u, v) && bob.union(u, v)) {
                ++count;
            }
        }
        for (int[] edge : edges) {
            int type = edge[0], u = edge[1] - 1, v = edge[2] - 1;
            if ((type == 1 && alice.union(u, v)) || (type == 2 && bob.union(u, v))) {
                ++count;
            }
        }

        if (alice.groups == 0 && bob.groups == 0) {
            return edges.length - count;
        } else {
            return -1;
        }
    }
}

JavaScript

/**
 * @param {number} n
 * @param {number[][]} edges
 * @returns {number}
 */
var maxNumEdgesToRemove = function (n, edges) {
    const alice = new UnionFind(n), bob = new UnionFind(n);
    let count = 0;

    for (let [type, u, v] of edges) {
        if (type === 3 && alice.union(u, v) && bob.union(u, v)) count++;
    }
    for (let [type, u, v] of edges) {
        if (
            (type === 1 && alice.union(u, v)) ||
            (type === 2 && bob.union(u, v))
        )
            count++;
    }

    if (!bob.groups && !alice.groups) return edges.length - count;
    else return -1;
};

/**
 * @class UnionFind
 * @param {number} n
 */
class UnionFind {
    constructor(n) {
        this.parent = new Array(n).fill().map((_, i) => i);
        this.groups = n - 1;
    }

    /**
     * @param {number} i
     * @returns {number}
     */
    find(i) {
        if (this.parent[i] !== i) this.parent[i] = this.find(this.parent[i]);
        return this.parent[i];
    }

    /**
     * @param {number} i
     * @param {number} j
     * @returns {boolean}
     */
    union(i, j) {
        const x = this.find(i),
            y = this.find(j);
        if (x === y) return false;
        else {
            this.parent[y] = x;
            this.groups--;
            return true;
        }
    }
}