「bzoj4998」星球联盟 - 并查集+LCA | Bill Yang's Blog

「bzoj4998」星球联盟 - 并查集+LCA

题目大意

    在遥远的S星系中一共有$N$个星球,编号为$1\ldots N$。其中的一些星球决定组成联盟,以方便相互间的交流。
    但是,组成联盟的首要条件就是交通条件。初始时,在这$N$个星球间有$M$条太空隧道。每条太空隧道连接两个星球,使得它们能够相互到达。若两个星球属于同一个联盟,则必须存在一条环形线路经过这两个星球,即两个星球间存在两条没有公共隧道的路径。
    为了壮大联盟的队伍,这些星球将建设$P$条新的太空隧道。这$P$条新隧道将按顺序依次建成。一条新轨道建成后,可能会使一些星球属于同一个联盟。你的任务是计算出,在一条新隧道建设完毕后,判断这条新轨道连接的两个星球是否属于同一个联盟,如果属于同一个联盟就计算出这个联盟中有多少个星球。


题目分析

考虑对原图缩点,每次缩点后原图的规模必定会减小。
每个点只可能被缩点一次,而缩点后块的大小即为每次询问的答案。

考虑使用并查集维护块,以深度最小的结点作为并查集的根。
那么每一次我们在缩点后的树上进行爬树爬到$lca$即可找到需要缩块的所有结点。

考虑,原图并不连通,且动态加边,如何维护出这样的一棵树呢?

我们可以离线处理,先离线将所有连通两个集合的DFS树边加入边集,对于其他的返祖边不予处理。
若原图仍不连通,强行使得其他的结点连向$1$。(这里的$1$可以换成其他的任何数,只要保证能连通,正确性在于这两个集合永远不会被合并掉,因此只要连起来就是可行的)

这样连通后预处理出树,每次暴力爬树并缩块即可。

本题与 「poj3694」网络 颇为相似。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=200005;
int n,m,q,prt[maxn],Ans[maxn],Depth[maxn],father[maxn],Size[maxn],top=0,cnt=0;
struct Point {
int x,y,opt;
Point(int _x=0,int _y=0):x(_x),y(_y),opt(0) {}
} a[maxn],b[maxn];
vector<int>edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
edges[y].push_back(x);
}
int Get_Father(int x) {
if(father[x]==x)return x;
return father[x]=Get_Father(father[x]);
}
void Dfs(int Now,int fa) {
prt[Now]=fa;
Depth[Now]=Depth[fa]+1;
for(int i=0; i<edges[Now].size(); i++) {
int Next=edges[Now][i];
if(Next==fa)continue;
Dfs(Next,Now);
}
}
int LCA(int x,int y) {
x=Get_Father(x);
y=Get_Father(y);
if(Depth[x]<Depth[y])swap(x,y);
while(Get_Father(x)!=Get_Father(y)) {
int Nowx=Get_Father(x),Nowy=Get_Father(prt[Nowx]);
if(Nowx!=Nowy) {
Size[Nowy]+=Size[Nowx];
father[Nowx]=Nowy;
}
x=Nowy;
if(Depth[x]<Depth[y])swap(x,y);
}
return Get_Father(x);
}
int main() {
n=Get_Int();
m=Get_Int();
q=Get_Int();
for(int i=1; i<=n; i++)father[i]=i;
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int();
int fx=Get_Father(x),fy=Get_Father(y);
if(fx!=fy) {
father[fy]=fx;
AddEdge(x,y);
} else b[++cnt]=Point(x,y);
}
for(int i=1; i<=q; i++) {
int x=Get_Int(),y=Get_Int();
int fx=Get_Father(x),fy=Get_Father(y);
if(fx!=fy) {
father[fy]=fx;
AddEdge(x,y);
a[i].opt=1;
}
a[i].x=x;
a[i].y=y;
}
for(int i=1; i<=n; i++) {
int x=Get_Father(1),y=Get_Father(i);
if(x!=y) {
father[y]=x;
AddEdge(1,i);
}
}
Dfs(1,0);
for(int i=1; i<=n; i++)father[i]=i,Size[i]=1;
for(int i=1; i<=cnt; i++)LCA(b[i].x,b[i].y);
for(int i=1; i<=q; i++)
if(a[i].opt!=1) {
int lca=LCA(a[i].x,a[i].y);
Ans[i]=Size[lca];
}
for(int i=1; i<=q; i++)
if(a[i].opt==1)puts("No");
else printf("%d\n",Ans[i]);
return 0;
0%