【题解】P1197 [JSOI2008]星球大战

发表于 分类于 阅读次数： Valine： 本文字数： 432 阅读时长 ≈ 2 分钟

（题目链接）

题目大意

给出$n$个节点，编号为$0$~$n-1$，给出$m$条无向边。接下来给出包含$k$个数的数列$p$，$p_i$表示第$i$步要删除编号为$p_i$的节点。

求每一步图中连通块的个数

$1\le m \le 2\times 10^5, 1\le n\le 2\times m$

分析

如果直接删除非常困难，想到从后向前处理，之后逆序输出即可。使用并查集判断联通性。

实现

$100pts,982ms,44.74mb$

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
#include<bits/stdc++.h>

using namespace std;
#define int long long
const int N = 400005;
int n, m, num, h[N], k, p[N], ans[N], fa[N];
int head[N], tmp;
struct node {
    int to = -1, next = -1;
} e[N << 2];
struct edge {
    int to, next;
} q[N];

void add(int x, int y) {
    e[++tmp].to = y;
    e[tmp].next = head[x];
    head[x] = tmp;
}

int find(int x) {
    if (fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}

void merge(int x, int y) {
    x = find(x);
    y = find(y);
    fa[y] = x;
}

int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        s = (s << 1) + (s << 3) + ch - '0';
        ch = getchar();
    }
    return s * w;
}

bool book[N];

signed main() {
    n = read(), m = read();
    for (int i = 1; i <= n; i++) fa[i] = i, head[i] = -1;
    for (int i = 1; i <= m; i++) {
        int x = read(), y = read();
        add(x, y);
        add(y, x);
        q[i * 2 - 1] = {x, y};
        q[i * 2] = {y, x};
    }
    k = read();
    for (int i = 1; i <= k; i++) {
        p[i] = read();
        book[p[i]] = true;
    }

    num = n - k;
    for (int i = 1; i <= 2 * m; i++) {
        if (!book[q[i].to] && !book[q[i].next] && find(q[i].to) != find(q[i].next)) {
            num--;
            merge(q[i].to, q[i].next);
        }
    }
    ans[k + 1] = num;
    for (int i = k; i >= 1; i--) {
        book[p[i]] = false;
        num++;

        for (int j = head[p[i]]; j != -1; j = e[j].next) {
            if (!book[e[j].to] && find(p[i]) != find(e[j].to)) {
                num--;
                merge(p[i], e[j].to);
            }
        }
        ans[i] = num;
    }

    for (int i = 1; i <= k + 1; i++) cout << ans[i] << endl;


    return 0;
}