P5058 [ZJOI2004] 嗅探器

简要题意

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

题目分析

前置芝士

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#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();
}