时间戳

首页 > 解决方案 > 在树中删除但只有一些节点

c++ - 在树中删除但只有一些节点

问题描述

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

这就是问题。我写了代码。但不知何故无法通过所有测试用例。我生成的所有测试用例都是真实的。你能告诉我为什么我错了。

您将获得 N 个目录/文件夹的目录树。每个目录由一个从 1 到 N 的特定表示。根目录的 id 为 1，然后它有一些子目录，这些目录可能包含其他一些目录，然后继续。现在您得到了一个要删除的目录 ID 列表，您需要找到需要删除的最小目录数，以便删除给定列表中的所有目录。

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

标签： c++algorithmgraphtree

解决方案

使用 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可能是一个有用的函数签名）。

推荐阅读