题目描述

给定一个包含 $N$ 个服务器实例的无向图（用邻接矩阵表示），以及两个特别的节点 $A$ 和 $B$。如果去掉某个中间节点 $C$（不包括 $A$ 和 $B$）后，原本所有连接 $A$ 到 $B$ 的路径都会被切断，则称节点 $C$ 存在单点故障风险。请列出所有这样的节点编号。

• 输入：
  • 第一行：整数 $N$（$3 \le N \le 20$）
  • 接下来 $N$ 行：$N\times N$ 的邻接矩阵 $M$，其中 $M[i][j]=1$ 表示 $i$ 与 $j$ 直接相连。
  • 最后一行：两个整数 $A$、$B$（节点编号，范围 $0$ 到 $N-1$）。
• 输出：
  • 将所有单点故障风险节点的编号（升序），用空格分隔。

解题思路

基本思路

我们要找的是「删除某个节点后，$A$ 与 $B$ 之间不再连通」的中间节点。直观的方法是：

1. 枚举每个候选节点 $c$（跳过 $A$ 和 $B$ 本身）。
2. 在图中「移除」节点 $c$（即视为已访问或不允许通过）。
3. 从 $A$ 出发做一次 DFS 或 BFS，看是否能到达 $B$。
4. 如果到达不了，则说明 $c$ 是单点故障风险节点。

相关算法

• 图的遍历：使用深度优先搜索（DFS）或广度优先搜索（BFS）检测连通性。
• 点割点评估：在小规模图（$N\le20$）上，直接枚举并每次做一次图遍历的复杂度足够。

复杂度分析

• 枚举每个节点：$O(N)$
• 每次 DFS/BFS：$O(N+E)$，在邻接矩阵下 $E=O(N^2)$，故一次遍历 $O(N^2)$。
• 总体时间复杂度：$O(N)\times O(N^2)=O(N^3)$。
• 由于 $N\le20$，最坏也只有 8000 次简单操作，足够快速。

代码实现

Python 版本

import sys
from collections import deque

def main():
    n = int(sys.stdin.readline().strip())
    adj = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
    a, b = map(int, sys.stdin.readline().split())
    res = []

    for c in range(n):
        if c == a or c == b:
            continue
        # 标记 c 为已访问，相当于移除
        vis = [False] * n
        vis[c] = True

        # 从 a 开始 BFS
        q = deque([a])
        vis[a] = True
        while q:
            u = q.popleft()
            for v in range(n):
                if adj[u][v] and not vis[v]:
                    vis[v] = True
                    q.append(v)

        # 如果 b 不可达，说明 c 是单点故障
        if not vis[b]:
            res.append(str(c))

    print(" ".join(res))

if __name__ == "__main__":
    main()

Java 版本

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] adj = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                adj[i][j] = in.nextInt();
            }
        }
        int a = in.nextInt(), b = in.nextInt();
        List<Integer> ans = new ArrayList<>();

        for (int c = 0; c < n; c++) {
            if (c == a || c == b) continue;
            boolean[] vis = new boolean[n];
            vis[c] = true; // 移除 c

            // BFS
            Queue<Integer> q = new LinkedList<>();
            q.offer(a);
            vis[a] = true;
            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v = 0; v < n; v++) {
                    if (adj[u][v] == 1 && !vis[v]) {
                        vis[v] = true;
                        q.offer(v);
                    }
                }
            }
            if (!vis[b]) {
                ans.add(c);
            }
        }
        // 输出结果
        for (int i = 0; i < ans.size(); i++) {
            System.out.print(ans.get(i) + (i + 1 < ans.size() ? " " : ""));
        }
    }
}

C++ 版本

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

int main() {
    int n;
    cin >> n;
    vector<vector<int>> adj(n, vector<int>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> adj[i][j];
    int a, b;
    cin >> a >> b;
    vector<int> res;

    for (int c = 0; c < n; c++) {
        if (c == a || c == b) continue;
        vector<bool> vis(n, false);
        vis[c] = true; // 移除 c

        // BFS
        queue<int> q;
        q.push(a);
        vis[a] = true;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v = 0; v < n; v++) {
                if (adj[u][v] && !vis[v]) {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
        if (!vis[b]) {
            res.push_back(c);
        }
    }

    // 输出
    for (int i = 0; i < (int)res.size(); i++) {
        cout << res[i] << (i + 1 < res.size() ? ' ' : '\n');
    }
    return 0;
}

题目内容

在某个系统的运行环境中，存在着很多服务器实例，服务器实例之间存在数据流动，假设原先从$A$到$B$服务器存在数据流动，即有一条或多条可用路径。如果某个服务器实例$C$(不包括起止点$A$和$B$)故障后，会导致$A、B$之间所有的数据流动路径中断，那么我们称服务器$C$是$A-B$线路上存在单点故障风险的服务器。已知服务器实例网络的数据流动图,请列出有单点故障的实例清单。

输入描述

第一行，$N$，服务器实例个数，$3<=N<=20$

第二行至第 $N+1$ 行，服务器节点之间的数据流向矩阵 $M$，$M[i,j]=1$表示 $i$ 和 $j$ 之间有数据流动，$M[i,j]=0$ 表示没有数据流动。

第 $N+2$ 行，起止服务器 $A、B$ 所对应的序号 ( $0$ 至 $N-1$ )

输出描述

请验出单点故障实例的数字编号(服务器编号从 $0$ 开始，$0$ 至 $N-1$)。有多个实例时，用空格隔开，排列顺序从小到大,本题绘出的所有用例一定存在单点故障实例。

样例1

输入

4
0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0
0 3

输出

1 2

说明

上述输入对应的图形如下：

图中有 $4$ 个节点：$0、1、2、3$

节点 $0-1$、节点 $1-2$、节点 $2-3$ 之间有数据流动。

上述输入节点 $1$ 和 $2$ 有单点故障风险，发生故障后会导致 $0-3$ 之间无法传输数据，因此输出为：$1$ $2$

样例2

输入

8
0 1 0 0 1 0 0 0
1 0 1 0 1 0 0 0
0 1 0 1 0 1 0 1
0 0 1 0 0 1 1 0
1 1 0 0 0 1 0 0
0 0 1 1 1 0 0 0
0 0 0 1 0 0 0 0
0 0 1 0 0 0 0 0
1 6

输出

3

说明

上述输入对应的图形如下：

对于 $A$ 和 $B$ 来说，只有服务然 $3$ 存在单点故障风险，因此输出为 $3$