题解：P14121 [SCCPC 2021] Don't Really Like How The Story Ends

· · 题解

题外话

这是一道可以加深你对 DFS 的理解的题目。

分析 & 思路

首先我们阅读题干，得知要通过补充若干条边，构造一张图，使得这张图的 DFS 序呈现 1 \sim n 的升序。

考虑从 DFS 的性质上进行分析。DFS 时，首先遍历当前节点的所有子节点，如果未被访问那么进行 DFS。遍历完所有点后返回。

设当前节点编号为 u，题目就是要使每次都遍历到编号为 u+1 的节点。根据上述 DFS 性质，这个条件成立有两个条件，满足其一即可成立：

如果上述条件均不成立，那么就要建边，使得当前节点可以访问编号为 u +1 的节点，也就是建立一条从编号为 u 的点到编号为 u + 1 的节点的边。

上面的两个条件可能有些复杂，所以下面我们通过例子来解释。

例子1

在这张图中，DFS 从 1 遍历到 3。此时 3 的子节点有 2、4 和 5，但是 2 已经被访问，所以 DFS 优先访问 4。4 = 3 + 1，成立。

但是如果图中没有从 3 到 4 的边，DFS 会访问到 5。此时我们就需要建立一条 3 到 4 的边。

例子2

在这张图中，DFS 访问到 4 时，4 已经没有可以访问的节点，此时它的祖先有 1、2 和 3（由 DFS 遍历而来）。在有未被访问的子节点的节点 1 和 2 中，2 离 4 更近，而且 2 也有 5 这个未被访问的子节点，5 = 4 + 1，成立。

但如果交换图中 5 和 6 的位置，2 会因为先访问到 6 而不成立，所以这时就要建立一条边。我们可以从 2、3 或 4 中任意一个点建立边，但为了代码方便，统一从当前点，也就是 4 建边到 5。

注意

我们找 ancestor_{u} 时可能相对困难，所以可以先记录每个点的父亲 fa_{i}。由于每个点只会被访问一次，所以 fa_{i} 不会改变。每次在判断上述条件 2（找 ancestor_{u}）时，可以通过跳 fa_{i} 的形式寻找最近的还有未被访问的子节点的祖先节点。找节点可能超时，所以要进行路径压缩。

最好用邻接表存图，然后对每个节点的子节点进行排序，这样可以用数组记录上一次访问的位置，也可以直接找到未被访问的编号最小的节点，节省时间。

代码

#include <bits/stdc++.h>
using namespace std;
int T;
int n, m;
vector<int> e[100005]; // 邻接表存图
void add(int u, int v)
{
    if (u > v)
        swap(u, v);
    e[u].push_back(v);
}
bool vis[100005];
int ans;
// 快速读入、输出
template <typename T>
void read(T &x)
{
    x = 0;
    T f = 1;
    char c = getchar();
    while (!isdigit(c))
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (isdigit(c))
    {
        x = x * 10 + (c - '0');
        c = getchar();
    }
    x *= f;
}
template <typename T>
void write(T x)
{
    if (x < 0)
        return putchar('-'), write(-x), void();
    if (x >= 10)
        write(x / 10);
    putchar(x % 10 + '0');
}

int fat[100005];      // 保存每个点的父亲，对应题解中的 fa
unsigned ptr[100005]; // 指针，用来记录之前访问到的位置

// 查询，对应条件 2
// res 记录答案  返回值 用来路径压缩
int res;
int find(int u, int k)
{
    if (u == 0)
    {
        res = -1;
        return 0;
    }
    if (ptr[u] < e[u].size())
    {
        while (ptr[u] < e[u].size())
        {
            if (e[u][ptr[u]] < k)
                ptr[u]++;
            else
                break;
        }
        if (ptr[u] < e[u].size())
        {
            if (e[u][ptr[u]] == k)
            {
                res = u;
                return u;
            }
            else
            {
                res = -1;
                return u;
            }
        }
    }
    if (fat[u] == 0)
    {
        res = -1;
        return 0;
    }
    else
        return fat[u] = find(fat[u], k); // 类似于并查集的路径压缩
}

void dfs(int u, int fa)
{
    fat[u] = fa;
    if (u == n)
        return;
    vis[u] = 1;
    while (ptr[u] < e[u].size())
    {
        if (e[u][ptr[u]] <= u)
            ptr[u]++;
        else
            break;
    }
    if (ptr[u] == e[u].size() || e[u][ptr[u]] > u + 1)
    {
        if (ptr[u] < e[u].size())
        {
            ans++;
            dfs(u + 1, u);
        }
        else
        {
            res = 0;
            find(fat[u], u + 1);
            int f = res;
            if (f == -1)
            {
                ans++;
                dfs(u + 1, u);
            }
            else
            {
                dfs(u + 1, f);
            }
        }
    }
    else
    {
        dfs(u + 1, u);
    }
}

// 多组数据，别忘了初始化清空
void clear()
{
    for (int i = 1; i <= max(n, m); i++)
    {
        fat[i] = 0;
        e[i].clear();
        vis[i] = false;
        ptr[i] = 0;
    }
    ans = 0;
}

int main()
{
    cin >> T;
    while (T--)
    {
        read(n);
        read(m);
        clear();
        for (int i = 1; i <= m; i++)
        {
            int u, v;
            read(u);
            read(v);
            add(u, v);
        }
        for (int i = 1; i <= n; i++)
        {
            sort(e[i].begin(), e[i].end()); // 排序，方便后续操作
        }
        dfs(1, 0);
        write(ans);
        putchar('\n');
    }
    return 0;
}