удаление в дереве, но только некоторый узел

Question

https://i.stack.imgur.com/JAz2M.png

это проблема.Я написал код.но как-то не в состоянии пройти все тестовые случаи.Все сгенерированные мной тесты соответствуют действительности.Можете ли вы сказать мне, почему я ошибаюсь.

Вам дано дерево каталогов N каталогов / папок.Каждый каталог представлен определенным значением в диапазоне от 1 до N. Идентификатор корневого каталога равен 1, затем у него есть несколько дочерних каталогов, эти каталоги могут содержать некоторые другие, и это продолжается.Теперь у вас есть список идентификаторов каталогов для удаления, вам нужно найти минимальное количество каталогов, которые нужно удалить, чтобы удалить все каталоги в данном списке.

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

использовать DFS!

Если корень помечен как «подлежащий удалению», верните 1 (это лучший случай, вы выполняете наименьшую работу). Иначе, вернитесь к каждому дочернему элементу корня и сложите их, чтобы узнать количество удаляемых узлов. Инвариант: если узел должен быть удален, не откажитесь от поддерева дальше (так как все, что находится в этом поддереве, в любом случае исчезнет)

Вот какой-то псевдокод

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;

У вас явно есть правильная идея представить дерево в виде списка смежности vector<vector<int>>.

Как второстепенная деталь, передайте список смежности как const& в рекурсию. Это экономит время копирования. (DFS(int root, const vector<vector<int>>& adjList может быть полезной сигнатурой функции).

Answer 2

Я решил то же самое с помощью Java. Ниже приведен код.

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