Table of Contents
Problem Statement
Remove Max Number of Edges to Keep Graph Fully Traversable Leetcode Solution- 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 be traversed by both Alice and Bob.
Given an array edges where edges[i] = [typei, ui, vi] represents a bidirectional edge of the 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 it’s impossible for the graph to be fully traversed by Alice and Bob.
Example
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:
Here we can notice that after removing the edges [1,1,2] and [1,1,3] the graph is still traversable by both Alice and bob, so the answer is 2.
Approach
Idea
The idea here is to think that initially the graph is empty and now we want to add the edges to the graph such that the graph is connected. Union-Find is the easiest way to solve such a problem where we start with all nodes in separate components and merge the nodes as we add edges into the graph.
As some edges are available to only Bob while some are available only to Alice, we will have two different union-find objects to take care of their own traversability. The key thing to remember is that we should prioritize type 3 edges over type 1 and 2 because they help both of them at the same time.
Algorithm
The main idea here is to connect the minimum edges so that all nodes become connected. For this, we think greedily and first process the edges of type 3.
For type 3 edges, if the path for Alice or bob is not connected then connect the path, or if the path for both Alice and bob exists then we remove this edge.
For type 2 edges, if the path for bob is connected then remove this edge otherwise connect the path.
Similarly for type 1 edges, if the path for Alice is connected then remove this edge otherwise connect the path.
After traversing through all the edges you will have your answer.
Code
C++ Code
class Solution {
public:
int find(int i,vector<int> &par){
if(par[i] == -1){
return i;
}
return par[i] = find(par[i],par);
//path compression.
}
bool union_set(int x,int y,vector<int> &par,vector<int> &rnk){
int s1 = find(x,par);
int s2 = find(y,par);
if(s1 != s2){
//union by rank.
if(rnk[s1] > rnk[s2]){
par[s2] = s1;
rnk[s1] += rnk[s2];
}
else{
par[s1] = s2;
rnk[s2] += rnk[s1];
}
return true;
}
return false;
}
int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
sort(edges.begin(),edges.end(),[](vector<int> &a,vector<int> &b){
return a[0] > b[0];
});
// To process the edges of type 3 first we sort the edges vector.
int rem = 0;
vector<int> parAlice(n,-1);
vector<int> parBob(n,-1);
vector<int> rnkAlice(n,1);
vector<int> rnkBob(n,1);
for(int i=0;i<edges.size();i++){
if(edges[i][0] == 3){
bool fg1 = union_set(edges[i][1]-1,edges[i][2]-1,parAlice,rnkAlice);
bool fg2 = union_set(edges[i][1]-1,edges[i][2]-1,parBob,rnkBob);
if(fg1==false && fg2==false){
//alice and bob are both connected to node x and node y so remove this edge.
rem += 1;
}
}
else if(edges[i][0] == 2){
bool fg2 = union_set(edges[i][1]-1,edges[i][2]-1,parBob,rnkBob);
if(fg2 == false){
//bob is connected to node x and node y so remove this edge.
rem += 1;
}
}
else{
bool fg1 = union_set(edges[i][1]-1,edges[i][2]-1,parAlice,rnkAlice);
if(fg1 == false){
//alice is connected to node x and node y so remove this edge.
rem += 1;
}
}
}
int co1=0,co2=0;
for(int i=0;i<n;i++){
if(parAlice[i]==-1){co1++;}
if(parBob[i]==-1){co2++;}
//if the nodes can be connected then there will be only one parent in the parent array.
}
if(co1==1 && co2==1){return rem;}
return -1;
}
};Java Code
class Solution {
public int maxNumEdgesToRemove(int n, int[][] edges)
{
Arrays.sort(edges, (a, b)->{
return b[0]-a[0];
});//giving the priority to third type of edge or the edge which Bob and Alice both can access
//1-based indexing of nodes
int []parentAlice= new int[n+1];//Graph 1 for Alice connectedness
int []parentBob= new int[n+1];//Graph 2 for Bob connectedness
for(int i= 0; i< n+1; i++){//every node is pointing to itself, at first no connection is considered all sets are independent(no dependency)
parentAlice[i]= i;
parentBob[i]= i;
}
//number of merged unique node for Alice and Bob that are required to maintain the connectedness of Alice and Bob graph nodes//intialised with one because merging happens in pair
int mergeAlice= 1;
int mergeBob= 1;
//number of cyclic or the non dependent node, that are not required for the connectedness of Alice and Bob nodes
int removeEdge= 0;
for(int []edge: edges)
{
int cat= edge[0];//category of edge 1)edge Alice can only access 2)edge Bob can only access 3)edge both Alice and Bob can access
int u= edge[1];
int v= edge[2];
if(cat == 3){//edge both Alice and Bob an access
//creating dependency of nodes in graph 1 and 2
boolean tempAlice= union(u, v, parentAlice);
boolean tempBob= union(u, v, parentBob);
if(tempAlice == true)
mergeAlice+= 1;
if(tempBob == true)
mergeBob+= 1;
if(tempAlice == false && tempBob == false)//retundant or the cyclic non-dependent edge//both Alice and Bob don't rquire it connection is already there between these pair of nodes
removeEdge+= 1;
}
else if(cat == 2){//edge Bob can only access
//creating dependency of nodes in graph 2
boolean tempBob= union(u, v, parentBob);
if(tempBob == true)
mergeBob+= 1;
else//no merging of set is done, that means that this edge is not required because it will form cycle or the dependency
removeEdge+= 1;
}
else{//edge Alice can only access
//creating dependency of nodes in graph 1
boolean tempAlice= union(u, v, parentAlice);
if(tempAlice == true)
mergeAlice+= 1;
else//no merging of set is done, that means that this edge is not required because it will form cycle or the dependency
removeEdge+= 1;
}
}
if(mergeAlice != n || mergeBob != n)//all node are not connected, connectedness is not maintained
return -1;
return removeEdge;//number of edge removed by maintaining the connectedness
}
public int find(int x, int[] parent)
{
if(parent[x] == x)//when we found the absolute root or the leader of the set
return x;
int temp= find(parent[x], parent);
parent[x]= temp;//Path Compression//child pointing to the absolute root or the leader of the set, while backtracking
return temp;//returning the absolute root
}
public boolean union(int x, int y, int[] parent)
{
int lx= find(x, parent);//leader of set x or the absolute root
int ly= find(y, parent);//leader of set y or the absolute root
if(lx != ly){//belong to different set merging
//Rank Compression is not done, but you can do it
parent[lx]= ly;
return true;//union done, dependency created
}
else
return false;//no union done cycle is due to this edge
}//Please do Upvote, it helps a lot
}Complexity Analysis for Remove Max Number of Edges to Keep Graph Fully Traversable Leetcode Solution
Time complexity
The time complexity of this approach is O(E), where E is the number of edges, as we are using path compression and union by rank so the find and union function become O(1) on average.
Space Complexity
The space complexity is also O(N), where N is the number of nodes.