题目链接 2016 CCPC 东北地区大学生程序设计竞赛 B 题
题意 给定一个无向图和一棵树, 树上的每个结点对应无向图中的一条边, 现在给出 $q$ 个询问,
每次选定树中的一个点集, 然后真正被选上的是这些点以及这些点的所有祖先
只有标号在树中真正被选上的点代表的这些原图中的边是存在的, 这样就构成了一个新的图求这个图的连通块个数
dfs 整棵树, 记 $f[x]$ 为若 $x$ 以及 $x$ 的所有祖先被选上, 那么构成的新的图的并查集)
这个实现比较简单, 搜索的时候打上标记, 回来的时候撤销即可
这样预处理的时间复杂度是 $O(nm)$ 的
然后对于每个询问, 把 $k$ 个询问的并查集全部合并就可以了
时间复杂度 $O(nm + kn)$
- #include <bits/stdc++.h>
- using namespace std;
- #define rep(i, a, b) for (int i(a); i <= (b); ++i)
- #define dec(i, a, b) for (int i(a); i >= (b); --i)
- #define MP make_pair
- #define fi first
- #define se second
- typedef long long LL;
- const int N = 523;
- const int M = 1e4 + 10;
- int T;
- int ca = 0;
- int n, m, q;
- int ans;
- int a[M], b[M], c[N], f[M][N];
- int father[N];
- vector <int> g[M];
- int getfather(int x){
- return father[x] == x ? x : father[x] = getfather(father[x]);
- }
- void dfs(int x, int fa){
- rep(i, 1, n) father[i] = f[fa][i];
- int fx = getfather(a[x]);
- int fy = getfather(b[x]);
- father[fx] = fy;
- rep(i, 1, n) father[i] = getfather(i);
- rep(i, 1, n) f[x][i] = father[i];
- for (auto u : g[x]){
- dfs(u, x);
- }
- }
- int main(){
- scanf("%d", &T);
- while (T--){
- printf("Case #%d:\n", ++ca);
- scanf("%d%d", &n, &m);
- rep(i, 0, m + 1) g[i].clear();
- rep(i, 2, m){
- int x;
- scanf("%d", &x);
- g[x].push_back(i);
- }
- memset(a, 0, sizeof a);
- memset(b, 0, sizeof b);
- rep(i, 1, m){
- scanf("%d%d", a + i, b + i);
- }
- rep(i, 1, n) f[0][i] = i;
- dfs(1, 0);
- scanf("%d", &q);
- while (q--){
- int y;
- scanf("%d", &y);
- rep(i, 1, n) father[i] = i;
- rep(i, 1, y){
- int x;
- scanf("%d", &x);
- memset(c, 0, sizeof c);
- rep(j, 1, n){
- int now = f[x][j];
- if (c[now]){
- int fx = getfather(c[now]);
- int fy = getfather(j);
- father[fx] = fy;
- }
- c[now] = j;
- }
- }
- ans = 0;
- memset(c, 0, sizeof c);
- rep(i, 1, n){
- int x = getfather(i);
- if (!c[x]) ++ans;
- c[x] = 1;
- }
- printf("%d\n", ans);
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2501083.html