P10521 瑟莉姆的宴会 Solution

OIerWu_829 · 2024-05-19 16:39:11 · 题解

题目传送门

由于题目保证有解，我们可以观察到：

• 不存在环，因为每个节点除了一个之外都有一个直接支配者；
• 有一个节点没有直接支配者，这个节点就是总支配者。

我们可以使用 DFS 或拓扑排序来构建这棵树，但有一个更简单的方法：

1. 遍历所有的支配条件，统计每个节点被支配的次数。
2. 找到没有被支配的节点作为根节点（总支配者）。
3. 从根节点开始，遍历所有剩余的节点，为每个节点分配一个直接支配者（除了根节点外，每个节点只有一个未被支配的节点）。

然后代码就出来了：

#include <iostream>
#include <vector>
#include <map>
using namespace std;
const int N = 1e5 + 10;
int n, m, a[N];
map<int, int> d1;
vector<int> G[N];
int Find() { // 找到根节点（总支配者）
    for (int i = 1; i <= n; i++)
        if (d1[i] == 0)
            return i;
    return -1;
}
void dfs(int nd, int p) { // 为每个节点分配直接支配者
    a[nd] = p;
    for (int nb : G[nd])
        if (a[nb] == 0) // 如果 nb 还没有被分配直接支配者
            dfs(nb, nd); // 递归分配
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        d1[y]++; // y 被 x 支配
        G[x].push_back(y); // 添加边 x -> y
    }
    int rt = Find(); // 找到根节点
    a[rt] = 0; // 根节点的直接支配者为 0
    dfs(rt, 0); // 从根节点开始分配直接支配者
    for (int i = 1; i <= n; i++)
        cout << a[i] << " ";
    return 0;
}