c/c++语言开发共享数据结构算法（n个点m条边连接删除问题）

题意，给定 n 个点，由 m 条无向边连接。现在，指定一个点删除，同时删除该点的邻边。问，余下的点最少要补多少条边才能够连通。

既然是连通性问题，就上并查集吧。因为有 k 个 case，先把边存下来。对于每个 case，遍历边集，将未被删除的边的两端加入并查集。遍历完成后，检查该并查集有多少个根（也就有多少个连通块)。由于用一条边就可将两个点连接起来，所以需要的边的数量是根数-1。

我用的 cin，第一发第五个点 t 了，关了同步后 ac。

另外，本题还可以用 dfs/bfs 做，就不写了。总之，思想就是找出删除某点后余下的图中连通块的数量。

#include <bits/stdc++.h>  using namespace std;  const int maxn = 1e3+3;  const int maxm = 1e6+6;  struct UnionFindSet {      int fa[maxn];      int sz[maxn];        UnionFindSet() {          for (int i = 0; i < maxn; ++i) {              fa[i] = i;              sz[i] = 1;          }      }        int find(int x) {          if (fa[x] != x) {              fa[x] = find(fa[x]);          }          return fa[x];      }        void unionSet(int x, int y) {          int rx = find(x), ry = find(y);          if (rx == ry) return;            if (sz[rx] < sz[ry]) swap(rx, ry);          fa[ry] = rx;          sz[rx] += sz[ry];      }  };    struct Edge {      int u, v;      Edge() {}      Edge(int u, int v): u(u), v(v) {}  } edges[maxm];  int n, m, k;    void read() {      cin >> n >> m >> k;      for (int i = 0; i < m; ++i) {          int u, v;          cin >> u >> v;          edges[i] = Edge(u, v);      }  }    int check(int occupied) {      UnionFindSet ust;      for (int i = 0; i < m; ++i) {          int u = edges[i].u, v = edges[i].v;          if (u != occupied && v != occupied) {              ust.unionSet(u, v);          }      }        bool isRoot[maxn] = {0};      for (int i = 1; i <= n; ++i) {          if (i != occupied) {              isRoot[ust.find(i)] = true;          }      }      int cnt = 0;      for (int i = 1; i <= n; ++i) {          if (isRoot[i]) {              ++cnt;          }      }      return cnt-1;  }    void solve() {      while (k--) {          int occupied;          cin >> occupied;          cout << check(occupied) << endl;      }  }    int main() {      ios::sync_with_stdio(false);      read();      solve();      return 0;  }

c/c++开发分享数据结构算法（n个点m条边连接删除问题）地址：https://blog.csdn.net/HNUCSEE_LJK/article/details/107870478