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

[mah-shamim]

Topics: Union Find, Graph

Alice and Bob have an undirected graph of n nodes and three types of edges:

• Type 1: Can be traversed by Alice only.
• Type 2: Can be traversed by Bob only.
• Type 3: Can be traversed by both Alice and Bob.

Given an array edges where edges[i] = [typei, ui, vi] represents a bidirectional edge of type typei between nodes ui and vi, find the maximum number of edges you can remove so that after removing the edges, the graph can still be fully traversed by both Alice and Bob. The graph is fully traversed by Alice and Bob if starting from any node, they can reach all other nodes.

Return the maximum number of edges you can remove, or return -1 if Alice and Bob cannot fully traverse the graph.

Example 1:

• Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
• Output: 2
• Explanation: If we remove the 2 edges [1,1,2] and [1,1,3]. The graph will still be fully traversable by Alice and Bob. Removing any additional edge will not make it so. So the maximum number of edges we can remove is 2.

Example 2:

• Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]
• Output: 0
• Explanation: Notice that removing any edge will not make the graph fully traversable by Alice and Bob.

Example 3:

• Input: n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]]
• Output: -1
• Explanation: In the current graph, Alice cannot reach node 4 from the other nodes. Likewise, Bob cannot reach 1. Therefore it's impossible to make the graph fully traversable.

Constraints:

• 1 <= n <= 105
• 1 <= edges.length <= min(105, 3 * n * (n - 1) / 2)
• edges[i].length == 3
• 1 <= typei <= 3
• 1 <= ui < vi <= n
• All tuples (typei, ui, vi) are distinct.

Hint:

1. Build the network instead of removing extra edges.
2. Suppose you have the final graph (after removing extra edges). Consider the subgraph with only the edges that Alice can traverse. What structure does this subgraph have? How many edges are there?
3. Use disjoint set union data structure for both Alice and Bob.
4. Always use Type 3 edges first, and connect the still isolated ones using other edges.

[mah-shamim]

We need to find the maximum number of edges that can be removed from an undirected graph such that the graph remains fully traversable by both Alice and Bob. The graph consists of three types of edges: type 1 (Alice only), type 2 (Bob only), and type 3 (both Alice and Bob). The solution involves using Union-Find (Disjoint Set Union, DSU) data structures to efficiently manage and check connectivity for both Alice and Bob.

Approach

1. Problem Analysis: The problem requires us to ensure that after removing some edges, both Alice and Bob can traverse the entire graph. This means the graph must remain connected for both Alice (using type 1 and type 3 edges) and Bob (using type 2 and type 3 edges). The goal is to maximize the number of edges removed while maintaining connectivity for both.

2. Intuition:

   • Priority for Type 3 Edges: Since type 3 edges can be used by both Alice and Bob, they are more valuable. We should process these edges first to connect as many nodes as possible for both users simultaneously.
   • Union-Find Data Structure: This helps efficiently manage and check connectivity. We maintain two separate Union-Find structures: one for Alice and one for Bob.
   • Edge Processing Order: Process edges in descending order of type (type 3 first, then type 1 and type 2). This ensures that type 3 edges are utilized first, optimizing connectivity for both users early on.

3. Algorithm Selection:

   • Union-Find: Used to manage the connected components for Alice and Bob. It supports two operations: find (to determine the root of a node) and union (to merge two sets).
   • Sorting Edges: Edges are sorted in descending order based on type to prioritize type 3 edges.
   • Connectivity Check: After processing all edges, verify if both Alice's and Bob's graphs are fully connected by checking if all nodes share the same root as node 1.

4. Complexity Analysis:

   • Time Complexity: Sorting the edges takes O(E log E), where E is the number of edges. The Union-Find operations (find and union) are nearly constant time due to path compression and union by rank, leading to an overall time complexity of O(E α(N)), where α is the inverse Ackermann function.
   • Space Complexity: O(N) for storing parent and rank arrays in the Union-Find structures, where N is the number of nodes.

Let's implement this solution in PHP: 1579. Remove Max Number of Edges to Keep Graph Fully Traversable

<?php
class UnionFind {
    private $parent;
    private $rank;

    public function __construct($n) {
        $this->parent = range(0, $n);
        $this->rank = array_fill(0, $n + 1, 1);
    }

    public function find($x) {
        if ($this->parent[$x] !== $x) {
            $this->parent[$x] = $this->find($this->parent[$x]);
        }
        return $this->parent[$x];
    }

    public function union($x, $y) {
        $rootX = $this->find($x);
        $rootY = $this->find($y);

        if ($rootX === $rootY) {
            return false;
        }

        if ($this->rank[$rootX] > $this->rank[$rootY]) {
            $this->parent[$rootY] = $rootX;
        } elseif ($this->rank[$rootX] < $this->rank[$rootY]) {
            $this->parent[$rootX] = $rootY;
        } else {
            $this->parent[$rootY] = $rootX;
            $this->rank[$rootX]++;
        }

        return true;
    }
}

/**
 * @param Integer $n
 * @param Integer[][] $edges
 * @return Integer
 */
function maxNumEdgesToRemove($n, $edges) {
    // Create two union-find instances for Alice and Bob
    $ufAlice = new UnionFind($n);
    $ufBob = new UnionFind($n);

    // Sort edges by type in descending order to prioritize type 3 edges
    usort($edges, function($a, $b) {
        return $b[0] - $a[0];
    });

    $requiredEdges = 0;

    foreach ($edges as $edge) {
        $type = $edge[0];
        $u = $edge[1];
        $v = $edge[2];

        if ($type === 3) {
            $unionAlice = $ufAlice->union($u, $v);
            $unionBob = $ufBob->union($u, $v);
            if ($unionAlice || $unionBob) {
                $requiredEdges++;
            }
        } elseif ($type === 1) {
            if ($ufAlice->union($u, $v)) {
                $requiredEdges++;
            }
        } elseif ($type === 2) {
            if ($ufBob->union($u, $v)) {
                $requiredEdges++;
            }
        }
    }

    // Check if both Alice and Bob can traverse the entire graph
    for ($i = 2; $i <= $n; $i++) {
        if ($ufAlice->find($i) !== $ufAlice->find(1) || $ufBob->find($i) !== $ufBob->find(1)) {
            return -1;
        }
    }

    return count($edges) - $requiredEdges;
}

// Example usage:
$n = 4;
$edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]];
echo maxNumEdgesToRemove($n, $edges); // Output: 2

$n = 4;
$edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]];
echo maxNumEdgesToRemove($n, $edges); // Output: 0

$n = 4;
$edges = [[3,2,3],[1,1,2],[2,3,4]];
echo maxNumEdgesToRemove($n, $edges); // Output: -1
?>

Explanation:

1. Union-Find Initialization: Two instances of the Union-Find data structure are created, one for Alice and one for Bob. These structures help manage the connected components for each user.
2. Edge Sorting: Edges are sorted in descending order based on type to prioritize type 3 edges, which benefit both users.
3. Edge Processing:
   • Type 3 Edges: Processed first. If connecting nodes in either Alice's or Bob's graph, the edge is counted as required.
   • Type 1 Edges: Processed next. Only counted if they connect nodes in Alice's graph.
   • Type 2 Edges: Processed last. Only counted if they connect nodes in Bob's graph.
4. Connectivity Check: After processing all edges, verify that both Alice's and Bob's graphs are fully connected by ensuring all nodes share the same root as node 1 in their respective Union-Find structures.
5. Result Calculation: The number of edges that can be removed is the total edges minus the required edges. If either graph is not fully connected, return -1.

This approach efficiently ensures the graph remains traversable for both users while maximizing the number of edges removed.

[topugit]

Thanks for solving the problem of "Remove Max Number of Edges to Keep Graph Fully Traversable"

[mah-shamim]

Thanks