题目描述
给出一个 $n$ 个点 $m$ 条边的无向图,点的编号为 $0$ ~ $n - 1$,起初每个点 $a_i$ 属于编号为 $i$ 的集合
共进行 $q$ 次操作,每次操作给出一个 $o$
如果没有点在编号为 $o$ 的集合中,那么无事发生
否则把和编号为 $o$ 的集合相邻的集合全部并入编号为 $o$ 的集合
最后求每个点所在的集合编号
$n, m, q \leq 8 × 10 ^ 5$
输入样例
1
4 3
0 1
1 2
2 3
4
0 1 3 0
输出样例
0 0 0 0
并查集 链表合并
使用存了尾节点下标的邻接表存图
每次合并集合的时候把要合并进来的那些点的邻接表连到根节点上
遍历过的边要清空一下,否则菊花图biss
时间复杂度 $O(能过)$
C++ 代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 800010, M = N << 1;
int h[N], t[N], e[M], ne[M], idx;
void add(int a, int b)
{
if(t[a] == -1) t[a] = idx;
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int p[N];
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
int _;
scanf("%d", &_);
while(_ --)
{
int n, m;
scanf("%d%d", &n, &m);
idx = 0;
for(int i = 0; i < n; i ++) h[i] = t[i] = -1, p[i] = i;
while(m --)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
scanf("%d", &m);
while(m --)
{
int u;
scanf("%d", &u);
if(p[u] != u) continue;
vector<int> points;
for(int i = h[u]; ~i; i = ne[i])
{
int j = find(e[i]);
if(j == u) continue;
p[j] = u;
points.push_back(j);
}
h[u] = t[u] = -1;
for(int j : points)
{
if(h[u] == -1)
{
h[u] = h[j];
t[u] = t[j];
}
else
{
ne[t[u]] = h[j];
t[u] = t[j];
}
}
}
for(int i = 0; i < n; i ++) printf("%d ", find(i)); puts("");
}
return 0;
}
$\mathcal O(能过)$这是啥时间复杂度......
听起来好高科技的样子......
$\text{O(能过)2333}$
2333好像是线性的,乘以一个并查集的那个常数