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

Question

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

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