[SDOI2008] 洞穴勘测

发表于 | 分类于 >
字数统计 : 327   |   阅读时长 ≈ 2 mins.

题目

链接

[SDOI2008]洞穴勘测

题意简述

使 个节点的一棵树支持 3种操作：

  • 连接 。
  • 断开 。
  • 查询 是否联通。

思路

暴力并查集

这很明显就是维护动态森林吧。
每次操作前先将 $x$ 提根。
连接时将 $y$ 设为 $x$ 的父亲。
断开时将 $y$ 的父亲设为 $0$ 。
暴力查询。
玄学复杂度。
时间复杂度： $O(?)$ 。
不过据说是随机数据所以跑得比香港记者还快。

LCT

我太蒻了，学了再补全。

代码

暴力并查集

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
#include <bits/stdc++.h>
#define REG register
#define IN inline
#define For(x,y,z) for (REG int (x) = (y); (x) <= (z); ++(x))
#define FOR(x,y,z) for (REG int (x) = (y); (x) <  (z); ++(x))
const int kmax_num = 1e4+ 10, kmax_int = 2147483647, kmod = 1e9+7;

int n, m;
int f[kmax_num];

inline void SPlay(REG int x)    {
    for(REG int a = 0, fa = f[x]; x; fa = f[x])
        f[x] = a, a = x, x = fa;
     return ;
}

int main() {
    std::cin >> n >> m;
    
    REG char cmd;
    REG int u, v;
    FOR(i,0,m)  {
        while(!isalpha(cmd = getchar()))    continue;
        std::cin >> u >> v;

        SPlay(u);

        if(cmd == 'C')          f[u] = v;
        else    if(cmd == 'D')  f[v] = 0;
        else    {
            for( ; u != v && v; v = f[v])   continue;
            puts(u == v ? "Yes" : "No");
        }
    }
	return 0;
}

杂项

  • 并查集提根就相当于翻转区间 。