洛谷P1197「JSOI2008」题解

发表于 | 评论数： | 阅读次数：

星战背景的并查集好题。

题目描述

很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治着整个星系。

某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。

但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始不可靠起来。

现在，反抗军首领交给你一个任务：给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序，以尽量快的速度求出每一次打击之后反抗军占据的星球的连通块的个数。（如果两个星球可以通过现存的以太通道直接或间接地连通，则这两个星球在同一个连通块中）。

输入输出格式

输入格式

输入文件第一行包含两个整数，N (1 < = N < = 2M) 和 M (1 < = M < = 200,000)，分别表示星球的数目和以太隧道的数目。星球用 0~ N-1 的整数编号。

接下来的 M行，每行包括两个整数 X, Y，其中（ 0 < = X <> Y表示星球 x 和星球 y之间有 “以太” 隧道，可以直接通讯。

接下来的一行为一个整数 k ，表示将遭受攻击的星球的数目。

接下来的 k 行，每行有一个整数，按照顺序列出了帝国军的攻击目标。这 k 个数互不相同，且都在 0到 n-1的范围内。

输出格式

第一行是开始时星球的连通块个数。接下来的 K 行，每行一个整数，表示经过该次打击后现存星球的连通块个数。

INPUT & OUTPUT’s examples

Input’s e.g. #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
8 13
0 1
1 6
6 5
5 0
0 6
1 2
2 3
3 4
4 5
7 1
7 2
7 6
3 6
5
1
6
3
5
7

Output’s e.g. #1

1
2
3
4
5
6
1
1
1
2
3
3

说明

[JSOI2008]

分析

这题第一眼看上去就是模拟！但显然模拟十分困难（实际是Herself32不会删边删点）。

所以我们思考一下逆向处理本题，把破坏改成修建不就好了吗。

然后我们通过并查集维护就好了。

首先计算出破坏$k$次之后还剩多少个点，然后用一个数组储存一个点的存亡与否。

然后枚举每一条边，如果这两个点都没有被打击，而且之前没有联通，那么就合并这两个点。

我们用一个ans[i]数组记一下破坏$i$次之后的答案。

这时ans[k+1] = tot。

然后我们从后往前修建以太隧道，遍历与这个点相连的边，如果被联通的点没有被破坏并且之前没有联通过，那么合并这两个点所在的集合，更新ans[]数组。

最后输出答案即可。

代码

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
inline void INC(int &x){
    x = x + 1; 
}
/* definitions */
const int MAXN = 4e5 + 10;
struct Edge{
    int from,to,next;
};
Edge Graph[MAXN];
int head[MAXN],cnt,n,m,K;
int aim[MAXN],UFS[MAXN],ans[MAXN]; 
bool alive[MAXN];
/* functions */
inline void Add_Edge(int from,int to){
    Graph[++cnt] = (Edge){from,to,head[from]};
    head[from] = cnt;
}
inline int Find(int x){
    if(x == UFS[x])return x;
    else return UFS[x]=Find(UFS[x]);
}
inline void unionx(int x,int y,int place){
    int findx = Find(x);
    int findy = Find(y);
    if(findx != findy){
        UFS[findy] = findx;
        ans[place]--;
    }
} 
inline void END_init(){
    FOR(i,1,n,1){
        if(alive[i] == true){
            int first = i;
            for(int j=head[first];j;j=Graph[j].next){
                int TO = Graph[j].to;
                if(alive[TO] == false)continue;
                int findx = Find(first), findy = Find(TO);
                if(findx != findy)UFS[findy] = findx, ans[K]--;
            }
        }
    }
}
int main(int argc,char *argv[]){
    scanf("%d%d",&n,&m);
    FOR(i,1,n,1)head[i]=0,alive[i] = true,UFS[i] = i;
    FOR(i,1,m,1){
        int u,v; scanf("%d%d",&u,&v);
        u++; v++;
        Add_Edge(u,v); Add_Edge(v,u);
    }
    scanf("%d",&K);
    ans[K] = n;
    FOR(i,1,K,1){
        scanf("%d",&aim[i]);
        aim[i]++; alive[aim[i]] = false;
        ans[K]--;
    }
    END_init();
    for(int i=K;i>=1;i--){
        ans[i - 1] = ans[i] + 1;
        int now = aim[i];
        for(int j=head[now];j;j=Graph[j].next){
            int TO = Graph[j].to;
            if(alive[TO] == false)continue;
            int findx = Find(now), findy = Find(TO);
            if(findx != findy)UFS[findy] = findx, ans[i-1]--;
        }
        alive[now] = true;
    }
    FOR(i,0,K,1)print(ans[i],false);
    return 0;
}

THE END