Remove maximum edges

Easy
0/40
Average time to solve is 15m
profile
Contributed by
6 upvotes
Asked in companies
AdobeWinZO

Problem statement

You are given an undirected graph with ‘N’ nodes and ‘M’ edges. There are two players P1 and P2, who want to traverse the complete graph. There are three types of edges in the graph, type 1 edges can be traversed by player P1, type 2 edges can be traversed by player P2, and type 3 edges can be traversed by both P1 and P2.

You are supposed to find the maximum number of edges that can be removed from the graph so that both players P1 and P2 can reach any node of the graph.

For Example :

Example

In the above graph, we can remove both the edges connecting node 1 and node 2(of type 1 and type 2). The graph will be fully traversable by only type 3 edges.


Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases. The test cases are as follows.

The first line of each test case contains two integers separated by a single space ‘N’ and ‘M’ denoting the number of the nodes and the number of edges respectively.

The next ‘M’ lines of each test case contain three integers “TYPE”, ‘X’ and ‘Y’ separated by a single space, here “TYPE” denotes the type of edge and ‘X’ and ’Y’ denote the vertices connected by an edge.
Output Format : 
For each test case, print the maximum number of edges that can be removed such that the graph is fully traversable by both P1 and P2 after removing the edges. If the graph cannot be fully traversed by P1 or P2 return -1.

Print the output of each test case on a new line.
Note : 
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 5
1 <= N <= 10^5
1 <= M <= 10^5
1 <= TYPE <= 3
1 <= X,Y <= N 

Where ‘T’ denotes the number of test cases, ‘N’ denotes the number of nodes in the graph, ‘M’ denotes the number of edges in the graph, “TYPE” denotes the type of edge, ‘X’ and ‘Y’ denote the nodes of the graph.

Time Limit: 1 sec
Sample Input 1 :
2
4 5
1 1 2
2 1 2
3 4 1
3 2 4
3 3 4
3 3
3 1 2
2 2 3
1 1 3
Sample Output 1 :
2
0
Explanation For Sample Input 1 :
In the first test case, we can remove 2 edges connecting node 1 and node 2(refer to the example above).

In the second test case, we cannot remove any edge as removing any edge will make the graph disconnected.
Sample Input 2 :
2
4 2
1 2 1
3 3 4
2 2
3 1 2
1 2 1
Sample Output 2 :
-1
1
Explanation For Sample Input 2 :
In the first test case, the graph is disconnected hence both the players cannot traverse all the nodes.

In the second test case, we can remove one edge of type 1.
Hint

Can you think about which type of edges should be traversed first? 

Approaches (2)
Union Find Approach

Suppose there are 3 edges from node 1 to node 2 of types 1,2 and 3. Now if both P1 and P2 are at node 1 and want to go to node 2, we can see that if both of them traverse the edge of type 3 then we can remove edges of type 1 and type 2, otherwise, we can remove at max 1 edge from node1 and node 2. From this observation, we can conclude that it is always optimal to traverse type 3 edges before traversing any other type of edge.  

   

The idea is to use the Disjoint Set Union(also known as Union Find) data structure and traverse the type 3 edges before traversing edges of type 2 and type 1. Initially, we will start with an empty graph and we will merge all connected nodes into a single component and keep track of the number of edges we are including to keep the graph connected.  

   

The steps are as follows :  

 

  1. Initially, none of the nodes is connected to any other node, hence each node is its own parent. We will declare a “PARENTONE” array, to keep track of the parent of each node for player 1 and another array “PARENTTWO” to keep track of the parent of each node for player 2. In both the arrays each element will initially be equal to its index number. We will use a variable "COUNT”(initially equal to 0) to count the number of edges that we are including in the graph.
  2. Let’s define two adjacency lists “PLAYERONE” and “PLAYERTWO” for storing the edges of type 1 and type 2 respectively.
  3. Iterate through the edges and for each edge of type 1 insert the edge into the adjacency list “PLAYERONE” and for edges of type 2 insert the edge into the adjacency list “PLAYERTWO”.
  4. For each edge of type 3, let’s say the nodes connected by this edge are ‘X’ and ‘Y’
  5. Find the parent nodes of ‘X’ and ‘Y’ for player 1, let’s denote them by “PARENTX” and “PARENTY”.
  6. If “PARENTX” and “PARENTY” are equal then it means that ‘X’ and ‘Y’ are already connected via some other path and hence we can safely remove this edge.
  7. Otherwise, apply the union operation on nodes ‘X’ and ‘Y’ i.e. PARENTONE[X]= PARENTONE[Y] and PARENTTWO[X]= PARENTTWO[Y](since both players can traverse this edge), and merge them into a single component, also increment "COUNT” by 1 since we include this edge in the graph.
  8. Let’s declare two variables "COUNTONE” and "COUNTTWO” to count the number of edges of type 1 and type 2 respectively which we will include in the graph. Both the variables will be initialized to 0.
  9. Iterate through all the edges in the adjacency list “PLAYERONE”  let’s say the nodes connected by this edge are ‘X’ and ‘Y’.
  10. Find the parent nodes of ‘X’ and ‘Y’ for player 1, let’s denote them by “PARENTX” and “PARENTY”.
  11. If “PARENTX” and “PARENTY” are equal then it means that ‘X’ and ‘Y’ are already connected via some other path and hence we can safely remove this edge.
  12. Otherwise, apply the union operation on nodes ‘X’ and ‘Y’ i.e. PARENTONE[X]= PARENTONE[Y], and merge them into a single component, also increment "COUNTONE” by 1 since we include this edge in the graph.
  13. Iterate through all the edges in the adjacency list “PLAYERTWO”  let’s say the nodes connected by this edge are ‘X’ and ‘Y’.
  14. Find the parent nodes of ‘X’ and ‘Y’ for player 2, let’s denote them by “PARENTX” and “PARENTY”.
  15. If “PARENTX” and “PARENTY” are equal then it means that ‘X’ and ‘Y’ are already connected via some other path and hence we can safely remove this edge.
  16. Otherwise, apply the union operation on nodes ‘X’ and ‘Y’ i.e. PARENTTWO[X]= PARENTTWO[Y], and merge them into a single component, also increment "COUNTTWO” by 1 since we include this edge in the graph.
  17. Now we have connected all the possible nodes, hence if the graph is connected then the edge count will be equal to N-1 (because we need at least one edge to connect 2 nodes, So for connecting ‘N’ nodes we will need N-1 edges) for both players, otherwise, it is not possible to traverse the complete graph. Hence if "COUNT” + "COUNTONE” or "COUNT” + "COUNTTWO” is not equal to N-1, we will return -1.
  18. Otherwise, the number of deleted edges will be given by ‘M’ - "COUNT” - "COUNTONE” - "COUNTTWO”, hence we will return this value.
Time Complexity

O(M*N), where ‘N’ is the number of nodes and ‘M’ is the number of edges in the graph.

 

We are iterating through all the edges and then finding the parent nodes for both nodes of each edge. There are ‘M’ edges and finding the parent node for each node can take O(N) time in the worst case when the graph forms a long chain-like structure. Thus, the overall time complexity is O(M*N).

Space Complexity

O(N), where N is the number of nodes in the graph.

 

We are creating adjacency lists for storing type 1 and type 2 edges which will take O(N) space. Thus, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Remove maximum edges
Full screen
Console