Remove Max Number Of Edges To Keep Graph Fully Traversable - Leetcode Solution

Problem Statement: Alice and Bob have an undirected graph of n nodes and 3 types of edges: Type 1: Can be traversed by Alice only Type 2: Can be traversed by Bob only Type 3: Can by traversed by both Alice and Bob Given an integer n and an array of edges where edges[i] = [type_i, u_i, v_i] represents a bidirectional edge of type type_i between nodes u_i and v_i. A node numbered i is said to be traversable by Alice if and only if Alice can reach any node j != i through edges type 1 or type 3, and a node j is said to be traversable by Bob if and only if Bob can reach any node k != j through edges type 2 or type 3. Return the maximum number of edges you can remove in such a way that after removing the edges, the graph can still be fully traversed by both Alice and Bob. If there are multiple answers, return the minimum among them.

Solution: We are given 3 types of edges and we can remove only type 1 and type 2 edges. We want to remove maximum number of edges so that traversal remains possible. Let's consider Alice and Bob separately. We will find the edges which are essential for the traversal of Alice and Bob.

For Alice: Create a group for all nodes that are connected through type 1 and type 3 edges. Let's say it is group1. In simple terms, nodes in group1 are connected through edges which can be traversed by Alice. Similarly, create another group for all nodes that are connected through type 2 and type 3 edges. Let's say it is group2. In simple terms, nodes in group2 are connected through edges which can be traversed by Bob.

Now, we want to remove maximum number of edges from these groups so that they are still connected. We will use Kruskal's algorithm to remove edges. We will first remove edges from group1 using Kruskal's algorithm. We will keep a count of the number of edges that we can remove while keeping the group1 connected. Let's say this count is X. Now, we will remove edges from group2 using Kruskal's algorithm. We will keep a count of the number of edges that we can remove while keeping the group2 connected. Let's say this count is Y.

To remove maximum number of edges, we can remove X + Y edges in total. So, the answer to the problem is n - 1 - (X + Y). The reason for subtracting (X + Y) is that we are considering edges, not nodes. So, the maximum number of edges is (n - 1), as there can be at most (n - 1) edges to make the graph connected.

Let's consider an example to understand the solution: n = 6, edges = [[1,1,2],[2,3,4],[3,4,5],[4,5,6],[1,2,3],[2,4,5],[3,5,6]] The graph looks like this:

We will create group1 and group2 as follows: group1 = {1, 2, 3} group2 = {4, 5, 6}

Now, we will find the number of edges that we can remove from group1 and group2 separately using Kruskal's algorithm. Let's first find edges that we can remove from group1.

group1_edges = [[1,1,2],[1,2,3],[3,4,5]] We cannot remove the edge [1,1,2], as it is the only edge that connects node 1 to group1. We cannot remove the edge [1,2,3], as it is the only edge that connects node 3 to group1. We can remove the edge [3,4,5], as it is an extra edge. So, X = 1.

Now, we will find the edges that we can remove from group2.

group2_edges = [[2,3,4],[2,4,5],[4,5,6]] We cannot remove the edge [4,5,6], as it is the only edge that connects node 6 to group2. We cannot remove the edge [2,3,4], as it is the only edge that connects node 3 to group2. We can remove the edge [2,4,5], as it is an extra edge. So, Y = 1.

Therefore, the maximum number of edges that we can remove is (n - 1) - (X + Y) = 6 - 1 - (1 + 1) = 3.

1