题面：[ZJOI2004] 嗅探器

大秦为你打开题目传送门

题目描述

某军搞信息对抗实战演习，红军成功地侵入了蓝军的内部网络。

蓝军共有两个信息中心，红军计划在某台中间服务器上安装一个嗅探器，从而能够侦听到两个信息中心互相交换的所有信息。

但是蓝军的网络相当的庞大，数据包从一个信息中心传到另一个信息中心可以不止有一条通路。

现在需要你尽快地解决这个问题，应该把嗅探器安装在哪个中间服务器上才能保证所有的数据包都能被捕获？

输入格式

输入文件的第一行一个整数 $n$，表示蓝军网络中服务器的数目。

接下来若干行是对蓝军网络的拓扑结构描述，每行是两个整数 $i,j$ 表示编号为 $i$ 和编号为 $j$ 的两台服务器间存在双向连接。

服务器的编号从 $1$ 开始，一行两个 $0$ 表示网络的拓扑结构描述结束，再接下来是两个整数 $a,b$ 分别表示两个中心服务器的编号。

输出格式

输出满足条件的服务器编号。如果有多个解输出编号最小的一个，如果找不到任何解，输出 No solution。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
5
2 1
2 5
1 4
5 3
2 3
5 1
0 0
4 2

样例输出 #1

1
1

提示

对于 $100\%$ 的数据，$1\le n\le 2 \times 10^5$，边数不超过 $5 \times 10^5$。

思路

显而易见的，想要控制所有信息，我们只需要设置在割点，所以我们直接处理出圆方树，然后找出 a -> b 路径上编号最小的割点就可以。

代码

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
// typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

const int MaxV = 2e5 + 10;
const int MaxE = 5e5 + 10;

template<int N, int M>
class Graph {
    private :
        struct Edge {
            int to, nt, wt;
            Edge() {}
            Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {}
        }e[M];
        int hd[N], cnte;
    public :
        inline void clear() { memset(hd, 0, sizeof(hd)), cnte = 0; }
        inline void AddEdge(int u, int v, int w = 0) {
            e[++cnte] = Edge(v, hd[u], w);
            hd[u] = cnte;
        }
        inline int head(int u) { return hd[u]; }
        inline int nt(int u) { return e[u].nt; }
        inline int to(int u) { return e[u].to; }
        inline int wt(int u) { return e[u].wt; }
};

int n, m;
Graph< MaxV, MaxE << 1 > G;
int sta, stb;

inline void Input() {
    read(n);
    int u = -1, v = -1;
    while(u != 0 && v != 0) {
        read(u, v);
        if(u == v) continue;
        m++;
        G.AddEdge(u, v);
        G.AddEdge(v, u);
    }
    read(sta, stb);
}

int dfn[MaxV], low[MaxV], cntd;
stack<int >st;
int cntc, col[MaxV];
Graph< MaxV << 1 , MaxE << 1 >T;

void Tarjan(int u, int fa) {
    dfn[u] = low[u] = ++cntd;
    if(u == fa && G.head(u) == 0) {
        col[u] = ++cntc;
        return ;
    }
    st.push(u); int ch = 0;
    for(int i = G.head(u); i; i = G.nt(i)) {
        int v = G.to(i);
        if(!dfn[v]) {
            Tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]) {
                cntc++; int now = 0;
                do {
                    now = st.top(); st.pop();
                    col[now] = cntc + n;
                    T.AddEdge(now, cntc + n);
                    T.AddEdge(cntc + n, now);
                    // cout << now << ' ' << cntc + n << endl;
                }while(now != v);
                T.AddEdge(cntc + n, u);
                T.AddEdge(u, cntc + n);
                // cout << u << ' ' << cntc + n << endl;
            }
        }
        else if(v != fa) {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

int vis[MaxV << 1];

inline int Bfs() {
    queue<pair<int , int > >q;
    q.push(make_pair(sta, 1e9));
    vis[sta] = 1;
    while(!q.empty()) {
        pair<int , int >f = q.front(); q.pop();
        if(f.first == stb) return f.second;
        for(int i = T.head(f.first); i; i = T.nt(i)) {
            int v = T.to(i);
            if(!vis[v]) {
                vis[v] = 1;
                q.push(make_pair(v, v != stb ? min(f.second, v) : f.second));
            }
        }
    }
    return 1e9;
}

inline void Work() {
    for(int i = 1; i <= n; i++) {
        if(!dfn[i]) Tarjan(i, i);
        // cout << "col" << i << " : " << col[i] << '\n';
    }
    int ans = Bfs(); 
    // cout << ans << endl;
    if(ans > n) printf("No solution\n");
    else printf("%d\n", ans);
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}