题解：P6255 [ICPC 2019 WF] Dead-End Detector

本题主要考察题意的转化，弄懂题目在说什么，问题就迎刃而解了。

思路

考虑把“死胡同”和“冗余”翻译成图论语言。

在无向图中，如果不掉头就回不去，意味着前方没有环。换句话说，沿着远离图中核心部分的方向进入树形结构，就相当于走进了死胡同。

由于树形结构里全都是死胡同，只要在进入这棵树的最外层入口插一个标志即可。因此，树内部的所有死胡同标志就都变成冗余的了。

我们只需要区分图中的环部分和外围树枝即可。这里可以使用类似拓扑排序“剥洋葱”的方法。

对于每个连通块，分两种情况讨论：

连通块内含环

标志应该放在离开环、进入外围树枝的第一步。

即：遍历连通块内的所有边，如果存在一条有向入口 $u \to v$ ，满足 $u$ 是没有被剥离的核心节点，且 $v$ 是被剥离的树枝节点，那么就需要记录一条答案。

进入这条边后，树枝内部的其他死胡同入口都可以依次到达，因此它们对应的标志都是冗余的。
连通块是纯树

因为整棵树中不存在环，所以从叶子节点沿着唯一的一条边向内走，一定会进入死胡同。

对于一个叶子节点，它只有唯一的一条相邻边，因此叶子指向内部的入口不可能被其他标志覆盖，必须加入答案。

而对于任意一个不是从叶子出发的入口，都可以在它后方的树形结构中找到一个叶子。从这个叶子的入口出发，可以一路走到当前入口，因此当前入口处的标志是冗余的。

所以，只需要找到该连通块中初始度数为 $1$ 的所有节点，将有向入口 $u \to v$ 加入答案，其中 $v$ 是 $u$ 唯一相邻的节点。

复杂度

每个节点和每条边只会被访问常数次，因此时间复杂度为 $O(n+m)$ ，空间复杂度为 $O(n+m)$ 。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;

int n, m;
vector<int> g[N];
int deg[N], odeg[N];
bool out[N], vis[N];

int main()
{
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        deg[u]++;
        deg[v]++;
        odeg[u]++;
        odeg[v]++;
    }

    queue<int> q;

    for (int i = 1; i <= n; i++)
    {
        if (deg[i] <= 1)
            q.push(i);
    }

    while (!q.empty())
    {
        int u = q.front();
        q.pop();

        out[u] = 1;

        for (int v : g[u])
        {
            if (!out[v])
            {
                deg[v]--;
                if (deg[v] == 1)
                    q.push(v);
            }
        }
    }

    vector<pair<int, int>> ans;

    for (int i = 1; i <= n; i++)
    {
        if (vis[i])
            continue;

        vector<int> cc;
        queue<int> bq;

        bq.push(i);
        vis[i] = 1;

        bool C = 0;

        while (!bq.empty())
        {
            int u = bq.front();
            bq.pop();

            cc.push_back(u);

            if (!out[u])
                C = 1;

            for (int v : g[u])
            {
                if (!vis[v])
                {
                    vis[v] = 1;
                    bq.push(v);
                }
            }
        }

        if (C)
        {
            for (int u : cc)
            {
                if (!out[u])
                {
                    for (int v : g[u])
                    {
                        if (out[v])
                            ans.push_back({u, v});
                    }
                }
            }
        }
        else
        {
            for (int u : cc)
            {
                if (odeg[u] == 1)
                {
                    for (int v : g[u])
                        ans.push_back({u, v});
                }
            }
        }
    }

    sort(ans.begin(), ans.end());

    cout << ans.size() << "\n";
    for (auto p : ans)
        cout << p.first << " " << p.second << "\n";

    return 0;
}