deletion in tree but only some node

Question

https://i.sstatic.net/JAz2M.png

this is the problem. I have wriiten code. but somehow not able to pass all test cases. All the test cases that I have generated they are true. Can you tell me why I am getting this wrong.

You are given a directory tree of N directories/folders. Each directory is represented by a particular which ranges from 1 to N. The id of the root directory is 1, then it has some child directories, those directories may contain some other ones and it goes on. Now you are given a list of directory id's to delete, you need to find the minimum number of directories that need to be deleted so that all the directories in the given list get deleted.

vector<vector<int> > adj;
vector<bool> del;
vector<bool> col;
void Final(int a, bool val)
{
    col[a] = val;
    if (del[a])
        val = del[a];
    for (int i = 0; i < adj[a].size(); i++) {
        Final(adj[a][i], val);
    }
    return;
}
int main()
{
    int n;
    cin >> n;
    adj.resize(n + 1);
    adj.clear();
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        adj[a].push_back(i);
    }
    int q;
    cin >> q;
    if (q <= 1) {
        cout << q << endl;
        return 0;
    }
    del.resize(n + 1);
    col.resize(n + 1);
    del.clear();
    col.clear();
    for (int i = 0; i <= n; i++) {
        col[i] = false;
        del[i] = false;
    }
    for (int i = 0; i < q; i++) {
        int a;
        cin >> a;
        del[a] = true;
    }
    if (del[1]) {
        cout << "1" << endl;
        return 0;
    }
    else {
        Final(1, false);
        int final = q;
        for (int i = 1; i <= n; i++) {
            if (del[i] && col[i])
                final--;
        }
        cout << final << " ";
    }
}

Answer 1

I have solved the same using Java. Below is the code.

// Function to add an edge into the graph
void addEdge(int v, int w) {
    adj[v].add( w); // Add w to v’s list.
}

 public int DFS(int s, Set<Integer> tset) {
   // Store the DFS travel which does not contain child nodes to be deleted
    List<Integer> dfs_travel = new Vector<>();
    // Initially mark all vertices as not visited
    List<Boolean> visited = new Vector<Boolean>(V);
    for (int i = 0; i <= V; i++)
        visited.add(false);

    // Create a stack for DFS
    Stack<Integer> stack = new Stack<>();

    // Push the current source node
    stack.push(s);

    while (stack.empty() == false) {
        // Pop a vertex from stack and print it
        s = stack.pop();

        // Stack may contain same vertex twice. So
        // we need to print the popped item only
        // if it is not visited.
        // Also check whether the element is part of elements to be remove
        if (visited.get(s) == false && tset.contains(s)) {
            dfs_travel.add(s);
            visited.set(s, true);
        }

        // Get all adjacent vertices of the popped vertex s
        // If a adjacent has not been visited, 
        // and it is not in delete set then push it
        // to the stack.
        if (!tset.contains(s)) {
            Iterator<Integer> itr = adj[s].iterator();
            while (itr.hasNext()) {
                int v = itr.next();
                if (!visited.get(v))
                    stack.push(v);
            }
        }
    }
    return dfs_travel.size();
}

private int processDirectoryDeletion(int n, int[] folders, int m,
        int[] idsTodelete) {
    TestClass g = new TestClass(n);

    Set<Integer> tset = new HashSet<Integer>();
    for (int i = 0; i < idsTodelete.length; i++) {
        tset.add(idsTodelete[i]);
    }
    g.addEdge(0, 1);
    int ans = 0;
    for (int i = 1; i < n; i++) {
        g.addEdge(folders[i], i + 1);
    }
    return g.DFS(1, tset);
  }

Answer 2

use DFS!

If the root is marked "to be deleted" return 1, (this is the best case, you do the least work). Else, recurse into every child of the root, and add them up to know the number of nodes to be deleted. The invariant is: if a node is to be deleted, do not recuse down the sub-tree any further (as everything rooted at this sub-tree is going to go away anyway)

Here is some pseudo-code

DFS(root)
    if(root is to be deleted)
        return 1
    else 
        number_of_nodes_to_delete = 0;
        for every child c of root
            number_of_nodes_to_delete += DFS(c)
        return number_of_nodes_to_delete;

You clearly have the right idea to represent the tree as an adjacency list vector<vector<int>>.

As a minor detail, pass in the adjacency list as const& into the recursion. This saves copy time. (DFS(int root, const vector<vector<int>>& adjList could be a useful function signature).