ABC315E 题解

啊这是一篇水文

题意就是，有 N 本书，每本书 i 需要在阅读前先阅读一些依赖的书；要求以最少阅读量完成书 1 的阅读，按照满足依赖关系的阅读顺序打印出必须阅读的除书 1 以外的书的编号。

就是个拓扑排序板子，但是为了满足最小阅读量，所以跑一遍深搜把不会访问到的点排除出点集就行。

Code:

void dfs(int u)
{
    vis[u] = 1;
    for (auto v : G[u]) {
        if (!vis[v])
            dfs(v);
    }
}

int main()
{
    io_init();
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> cnt;
        deg[i] = cnt;
        G[i].reserve(cnt);
        for (int j = 1; j <= cnt; j++) {
            cin >> v;
            G[i].push_back(v);
            rg[v].push_back(i);
        }
    }
    dfs(1);
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) deg[i] = -1;
    }
    for (int i = 1; i <= n; i++) {
        if (deg[i] == 0)
            q.push(i);
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        rd.push_back(u);
        for (int v : rg[u]) {
            if (--deg[v] == 0)
                q.push(v);
        }
    }
    for (int x : rd) if (x != 1) cout << x << ' ';
    return 0;
}