描述

在网络中关键节点的判断将成为影响网络连通性的主要因素。节点之间通过关键节点传递信息，如在我们以太网中的网关。当网关节点失效，那么两个网络之间的节点就不能够进行通信。在无线传感器网络中，会造成不能及时监控部分区域的信息。这次请编写程序主要实现一个简单的判断关键节点方法。

关键节点的定义：在图中有那么一些特殊的节点，如果去除这些点，则会使得从某个初始节点到某个终止节点的这两个节点变得不连通。这些点被称为最短路径上的关键点。现举例说明如下：

如图所示，若网络结构由6个节点组成，从节点1到节点6之间是连通的，并且有两个关键节点3和5。也就是说，如果这两个节点任何一个失效了，1到6就不能连通了。但是节2，节点4失效，不会影响1到6的连通。

现给定一个无权图，以及起始节点和终止节点，要求输出该图上，这对节点间的关键点数目。

输入

多组数据测试，每组测试数据如下：
输入多行：
第1行：输入节点数N（N<=1000）的路径数roat（N(N-1)/2<=roat<=3N）
第2行：第2+roat-1行： 输入每一节路径的起点与终点
第2+roat行：输入需查验的起点与终点
输出一行：
关键节点数

输出

每组输出一行：
关键节点数

样例输入

6 6   
1 3    
2 3    
3 4    
3 5   
4 5    
5 6   
1 6    

样例输出

2

思路

用并查集的数据结构解决
遍历所有节点（for (int i = 1; i <= n; i++)）

重置并查集状态：考虑每个节点i时，重置并查集转态，考虑，以便独立测试节点i是否是关键节点
构建不包含当前节点的图：遍历所有边，若边的两个端点都包含节点i，则将两个端点合并到一个集合
检查连通性：移除节点i后，检查起点x和起点y是否连通（即看find(pre)是否相等），若不连通，说明节点i时关键节点

code

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
typedef pair<int, int> PII;
int pre[maxn];
void init() {
    for (int i = 1; i < maxn; i++) {
        pre[i] = i;
    }
}
int find(int x) {
    return pre[x] == x ? x : pre[x] = find(pre[x]);
}
void merge(int x, int y) {
    int rootx = find(x);
    int rooty = find(y);
    if (rootx != rooty) {
        pre[rootx] = rooty;
    }
}
int main()
{
    int n, m;
    while (cin >> n >> m) {//操作数
        vector<PII> road;
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            road.push_back({ a,b });
        }
        int x, y;//查验起点、终点
        cin >> x >> y;
        int ans = 0;//关键点个数
        for (int i = 1; i <= n; i++) {
            if (i == x || i == y) continue;//起始点和终点不是关键节点 
            init(); 
            for (int j = 0; j < m; j++) {//遍历所有的边 
                PII temp = road[j];//获取第j条边的起点、终点 
                if (temp.first != i && temp.second != i) {
                //若j条边的起点、终点都不是当前节点i,则这条边就不会被当前节点阻断 
                    merge(temp.first, temp.second);
        //将边的起点和终点合并至一个集合中,模拟这条边连接作用 
                }
            }
            if (find(x) != find(y)) ans++;
            //在排除节点i后,检查x和y是否联通,若不联通,说明节点i为一个关键节点 
        }
        cout << ans << endl;
    }
    return 0;
}