Last Updated: 18 Mar, 2021
Remove Edges
Moderate
Asked in companies
You are given an undirected graph with ‘N’ vertices and ‘M’ edges. Each edge has a particular type as described below:
An edge with type 1 can only be traversed by a person ‘A’.
An edge with type 2 can only be traversed by a person ‘B’.
An edge with type 3 can be traversed by both persons ‘A’ and ‘B’.
Your task is to determine the maximum number of edges that can be removed such that after removing these edges, all the nodes can still be traversed by both ‘A’ and ‘B’.
Input Format:
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the ‘T’ test cases follow.
The first line of each test case contains two space-separated integers, ‘N’, denoting the total number of nodes, and ‘M’, denoting the total number of edges.
Then ‘M’ lines follow. Each of which has three space-separated integers, ‘X’ ‘Y’, and ‘Z’.
‘X’ denotes the type of edge. ‘Y’ and ‘Z’ denote the two nodes between which the edge is present.
Output Format:
For each test case, print a single line containing a single integer denoting the maximum number of edges that can be removed.
The output for each test case will be printed in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N,M < 10 ^ 4
edges[i].length = 3
1 <= edges[i][0] <= 3
1 <= edges[i][1], edges[i][1] <= N
Where ‘T’ is the number of test cases, ‘N’ is the total number of nodes, ‘M’ is the total number of edges and edges[i] describes the i-th edge
Time Limit: 1 sec.
Approaches
Approach
The approach is to use Union-Find to find out the minimum number of edges that are required to make the graph a single connected component for both ‘A’ and ‘B’. Since using an edge of type 3 can minimize the total number of edges needed, we will consider these first. Finally, after considering all the edges, if the entire graph can be traversed by both A and B, we print the number of edges that were not needed, else we print “-1”.
Steps
- Define a class UnionFind and create two objects of it, typeA(N) and typeB(N), where N is the number of nodes.
- Initialize a variable addedEdges = 0 to store the count of edges that were added in order to make the graph traversable for both A and B.
- Run a loop from i=0 to i=edges.size() and do:
- Define edgeType = edges[i][0].
- Define node1 = edges[i][1] and node2 = edges[i][2].
- Since we are considering edges of type3 first, if(edgeType!=3) continue.
- Now, if node1 and node2 are not connected either by type1 edge or by type2 edge, we connect these nodes by a type3 edge and increment the counter. Formally, if(typeA.ifNotConnected(node1,node2) or typeB.ifNotConnected(node1,node2) addEdges++.
- Now, again run a loop from i=0 to i=edges.size() and do:
- Define edgeType = edges[i][0].
- Define node1 = edges[i][1] and node2 = edges[i][2].
- If edgeType==1 and typeA.ifNotConnected(node1,node2), addEdges++.
- If edgeType==2 and type2.ifNotConnected(node1,node2), addEdges++.
- Now, if typeA and typeB both have a singly connected component, then return the number of edges that were not required, which is equal to edges.size - addedEdges.
- Else, return “-1”.
class UnionFind {
- Initialize a vector say component to keep track of which node belongs to which component.
- Initialize a variable say numOfComponents to store the number of total distinct components.
- Create a constructor UnionFind(n) {
- numOfComponents = n.
- For all i=0 to i=n, push i in component.
- findComponent(a) {
- if(component[a] != a) component[a] = findComponent(component[a])
- Return component[a].
- ifNotConnected(node1, node2) {
- If both nodes belong to the same component, i.e if(findComponent(node1) == findComponent(node2)) return false.
- Else connect them by making component[findComponent(a)] = b.
- Decrease numOfComponents by one and return true as they are connected.
- singlyConnected() {
- If numOfComponents == 1, return true.