题意,给定 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
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/598245.html