嗅探器

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1414 字
给n个点的无向图，边读到00为止，再给两个信
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1523
// 题意：给 n 个点的无向图，边读到 0 0 为止，再给两个信息中心 a、b，求编号最小的中间点 x（x 不等于 a、b），使删掉 x 后 a 与 b 不连通；无解输出 No solution。
// 思路：枚举每个非中心点 x，把它标记成禁行后从 a 做一次 BFS，若到不了 b 则 x 就是答案，找到第一个（编号从小到大枚举）即可输出。
// 1. n 不超过 100，枚举加点 BFS 的复杂度完全够用，不需要写 Tarjan 判断割点后再分类讨论。
// 2. 从小到大枚举保证输出的是编号最小的解，一旦命中就可以直接结束程序。
// 复杂度：O(n * (n + m)) 时间 / O(n + m) 空间
// 易错点：a 和 b 自身不能作为嗅探器的安放位置，枚举时必须跳过这两个点。
// 易错点：删掉的是点 x 本身，BFS 时不仅不能走到 x，也不能从 x 继续扩展，入队前就要判断。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
vector<int> g[MAXN];
int main(){
    int n;
    if(!(cin >> n)) return 0;
    while(true){
        int a, b;
        if(!(cin >> a >> b)) return 0;
        if(a == 0 && b == 0) break;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int A, B;
    if(!(cin >> A >> B)) return 0;
    for(int x = 1; x <= n; x++){
        if(x == A || x == B) continue;
        vector<int> vis(n + 1, 0);
        vis[x] = 1;
        queue<int> q;
        q.push(A);
        vis[A] = 1;
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(int k = 0; k < (int)g[u].size(); k++){
                int v = g[u][k];
                if(vis[v]) continue;
                vis[v] = 1;
                q.push(v);
            }
        }
        if(!vis[B]){
            cout << x << "\n";
            return 0;
        }
    }
    cout << "No solution" << "\n";
    return 0;
}
嗅探器

正文

一本通·提高篇的其它内容
