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);
            }
        }
    }
}