Last Updated: 3 Jan, 2021
Remove maximum edges
Easy
Asked in companies
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 :
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.
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
Approaches
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 :
- 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.
- Let’s define two adjacency lists “PLAYERONE” and “PLAYERTWO” for storing the edges of type 1 and type 2 respectively.
- 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”.
- For each edge of type 3, let’s say the nodes connected by this edge are ‘X’ and ‘Y’
- Find the parent nodes of ‘X’ and ‘Y’ for player 1, let’s denote them by “PARENTX” and “PARENTY”.
- 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.
- 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.
- 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.
- Iterate through all the edges in the adjacency list “PLAYERONE” let’s say the nodes connected by this edge are ‘X’ and ‘Y’.
- Find the parent nodes of ‘X’ and ‘Y’ for player 1, let’s denote them by “PARENTX” and “PARENTY”.
- 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.
- 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.
- Iterate through all the edges in the adjacency list “PLAYERTWO” let’s say the nodes connected by this edge are ‘X’ and ‘Y’.
- Find the parent nodes of ‘X’ and ‘Y’ for player 2, let’s denote them by “PARENTX” and “PARENTY”.
- 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.
- 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.
- 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.
- Otherwise, the number of deleted edges will be given by ‘M’ - "COUNT” - "COUNTONE” - "COUNTTWO”, hence we will return this value.
The idea is to use a path compression algorithm for finding the parent of each node. Once we traverse a node we will change its parent node to the leader node of the whole component so that the next time we traverse the same node we can directly get the leader node of the component in O(1) time. Also, we will use the union by size optimization to merge two components. We will keep track of the size of each component and always merge the smaller component into the larger component.
We will use the Disjoint Set Union(also known as Union Find) data structure with the path compression optimization 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 :
- 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.
- Let’s define two adjacency lists "PLAYEROne” and "PLAYERTwo” for storing the edges of type 1 and type 2 respectively.
- 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”. For each edge of type 3, let’s say the nodes connected by this edge are ‘X’ and ‘Y’ .
- Find the parent nodes of ‘X’ and ‘Y’ for player 1, let’s denote them by "PARENTX” and "PARENTY”. 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.
- 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.
- 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.
- Iterate through all the edges in the adjacency list "PLAYERONE” let’s say the nodes connected by this edge are ‘X’ and ‘Y’.
- Find the parent nodes of ‘X’ and ‘Y’ for player 1, let’s denote them by "PARENTX” and "PARENTY”.
- 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.
- 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.
- Iterate through all the edges in the adjacency list "PLAYERTWO” let’s say the nodes connected by this edge are ‘X’ and ‘Y’
- Find the parent nodes of ‘X’ and ‘Y’ for player 2, let’s denote them by "PARENTX” and "PARENTY”.
- 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.
- 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.
- 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.
- Otherwise, the number of deleted edges will be given by ‘M’ - "COUNT” - "COUNTONE” - "COUNTTWO”, hence we will return this value.