TC: O(n*m) where n is the no. of nodes and m is the max no. of nodes/methods present in a component (directly and indirectly initialized by k (given) with no external invocation) that needs to be removed
class Solution {
public List<Integer> remainingMethods(int n, int k, int[][] invocations) {
List<Integer> result = new ArrayList<>();
//Prepare two adjacency lists, 1 for finding all the methods invoked by k,
// another for DFS traversal of the nodes
List<List<Integer>> adj = new ArrayList<>();
List<List<Integer>> adj2 = new ArrayList<>();
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
adj2.add(new ArrayList<>());
}
for (int i = 0; i < invocations.length; i++) {
//Keep the adjacency directional only for finding all methods invoked by k
// that will be considered as a component that needs to be removed in present in
// the graph
adj2.get(invocations[i][0]).add(invocations[i][1]);
//For DFS traversal make the edges bi-directional in adjacency
//This will help us to tackle the edge case
/*
* e.g n =3, k =0, [[2,0]] there is an edge from 2 to 0,
* now, DFS will help us find all the components in the above graph
* since k = 0, and 0 and other nodes that it invokes can only be removed if
* they are not invoked externally by any other nodes but in the example
* node 0 is involved by 2.
*
* If we do DFS (with directed adjacency) on the graph we will get 3 components
* 0,1,2 ( which should not be the case as there are only 2 components i.e (1),
* (2,0))
* This is happening because we choose directed adjacency and from 0 there
* is no direct edge to any other node, So DFS traversal will assume it to be a
* component ( which is wrong)
* Hence while creating components we will make the adjacency list
* bi-directional that way components created will be
* (0,2) and (1)
* and Since we will be using directed adjacency for finding all the
* methods/nodes invoked by k. It will create a component of nodes (directly or
* indirectly invoked by k only ) i.e 0 only
*/
adj.get(invocations[i][0]).add(invocations[i][1]);
adj.get(invocations[i][1]).add(invocations[i][0]);
}
// keep track of nodes that need to be removed if a component has only these
// nodes
int dc[] = new int[n];
List<Integer> dcn = new ArrayList<>(); // dcn component that needs to be removed
prepareDcDfs(k, dc, adj2, dcn);
int visited[] = new int[n];
for (int i = 0; i < n; i++) {
if (visited[i] == 0 && dc[i] == 0) { // only traverse the nodes that are not visited and are not part of
// dcn, that needs to be removed to save time
List<Integer> l = new ArrayList<>();// keep track of nodes in each component
dfs(i, visited, adj, l);
if (l.size() != dcn.size()) { // if the component l, is not equal to dcn, this is not the
// component we want to remove
result.addAll(l);
} else {// if found a component l, having the same size as dcn, check individual nodes
// to make sure that l has all the nodes present in dcn that needs to be removed
for (int node : l) {
if (!dcn.contains(node)) {// if not the same component then l should not be removed and shoud be
// part of final node list i.e result
result.addAll(l);
break;
}
}
}
}
}
return result;
}
// DFS to find nodes invoked by k directly or indirectly (using directed
// adjacency)
public void prepareDcDfs(int node, int dc[], List<List<Integer>> adj, List<Integer> dcn) {
dc[node] = 1;
dcn.add(node);
for (int adjNode : adj.get(node)) {
if (dc[adjNode] == 0)
prepareDcDfs(adjNode, dc, adj, dcn);
}
}
// dfs to find all components in the given graph using bi-directional adjacency
public void dfs(int node, int visited[], List<List<Integer>> adj, List<Integer> list) {
visited[node] = 1;
list.add(node);
for (int adjNode : adj.get(node)) {
if (visited[adjNode] == 0) {
dfs(adjNode, visited, adj, list);
}
}
}
}
Top comments (0)