题解 洛谷 P5058 [ZJOI2004] 嗅探器

P5058 [ZJOI2004] 嗅探器

简要题意

给定一张图，再给处图中两个点 $x,y$，现在要在图中删去除了 $x,y$ 以外的一个点使得 $x$ 和 $y$ 不再连通，求要删除的点的编号

题目分析

前置芝士

题目要求我们删掉一个点使得给定的两个点不连通，那么其实我们就是要找一个满足要求的割点，如下图标黑的点就是题目给定的两个点：

点 $1$ 是一个割点，我们删除点 $1$ 即可使得 $2,4$ 两点不连通，但是并非任意割点都满足要求，比方说下面这张图：

点 $3$ 和点 $4$ 都是图中的割点，但是删去 $4$ 并不能使得目标点 $1,7$ 不连通，所以只有点 $3$ 是符合条件的点，那么我们就要去筛选割点中符合要求的点。

怎么筛呢？其实我们想一想建立 DFS 树的过程，我们从题中给定的一个点开始搜，那么对于一个符合条件的割点来讲，题中给定的另一个点一定在这个符合条件的割点的子树中。所以在搜的时候加个判断条件就好了。本题因为不能删去根，所以不用考虑根是割点的情况，那么代码也就非常简单：

#include <iostream>
#include <cstdio>
using namespace std;

namespace SHAWN {
    const int N = 1e6 + 7;
    int head[N], cnt;
    struct edge { int to, next; }edge[N];
    int n, tim, x, y;
    int dfn[N], low[N];
    bool vis[N], flag[N];

    inline void add(int u, int v) {
        edge[++cnt].next = head[u];
        edge[cnt].to = v;
        head[u] = cnt;
    }

    void Tarjan(int u, int fa) {
        low[u] = dfn[u] = ++tim;
        vis[u] = true;
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].to;
            if (!vis[v]) {
                Tarjan(v, u);
                low[u] = min(low[u], low[v]);
                // 这里多加一个u!=x和dfn[y]>=dfn[v]的特判就OK了
                if (fa != u && low[v] >= dfn[u] && u != x && dfn[y] >= dfn[v]) {
                    flag[u] = true;
                }
            }
            else if (fa != v) {
                low[u] = min(low[u], dfn[v]);
            }
        }
    }

    int work()
    {
        cin >> n;
        while (cin >> x >> y && x && y) {
            add(x, y); add(y, x);
        }
        cin >> x >> y;
        Tarjan(x, x);
        for (int i = 1; i <= n; ++i) {
            if (flag[i]) {
                cout << i << '\n';
                return 0;
            }
        }
        cout << "No solution\n";
        return 0;
    }
}

signed int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}