[JSOI2008] 星球大战
题目描述
给定一张无向图G=(n,m),共有n个点和m条边,没有边权。在k的时间范围之内,会依次删除一些点。求出t=0 \sim k时的连通块个数。
样例 #1
样例输入 #1
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
样例输出 #1
1
1
1
2
3
3
提示
【数据范围】
对于 100\% 的数据,1\le m \le 2\times 10^5,1\le n \le 2m,x \neq y。
分析
连通块的个数可以用并查集确定,但是并查集如何删除连接?这是一个问题。
于是我们将时间倒过来,先将所有该拆的点都拆掉,慢慢加回来,此时我们只需要看依次加回来的点是否跟剩下的图连通。
注意删除一个点之后,在未被删除中的点中判断连通块。
做法
1.初始化原图,使用链式前向星建图。
2.读入删除顺序,建立一个vis数组,将删除的点全部标记为1。
3.初始化一个tot变量,这是此时的连通块数量,值为n-k。
4.跑一遍所有的边,如果该边两头的点vis=0,连接并tot–。
5.倒序加点,初始化tot++,查看这个点的所有边,如果可以连通,连接并tot–。
Code
#include
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const int M = 2e5 + 10;
const int N = 4e5 + 10;
int n, m, k;
int x, y, z[M];
int vis[N];
struct edge{int from, to, nxt;}G[M << 1]; // 链式前向星
int cnt = 1, head[N];
inline void add_edge(int u, int v) {G[cnt] = (edge){u, v, head[u]}; head[u] = cnt++;}
int fa[N]; //并查集
inline void init() {for(int i = 1; i <= n; i++) {fa[i] = i;} memset(head, -1, sizeof(head));}
int find(int pos) {if(fa[pos] != pos) {fa[pos] = find(fa[pos]);} return fa[pos];}
inline void merge(int posx, int posy) {if(find(posx) != find(posy)) fa[find(posx)] = find(posy);}
inline int check(int posx, int posy) {return find(posx) == find(posy);}
int main()
{
scanf("%d%d", &n, &m);
init();
for(int i = 1; i <= m; i++) {
scanf("%d%d", &x, &y);
add_edge(x, y);
add_edge(y, x);
}
scanf("%d", &k);
for(int i = 1; i <= k; i++) {
scanf("%d", &z[i]);
vis[z[i]] = 1;
}
stack ans;
int tot = n - k;
for(int i = 1; i <= m << 1; i++) {
if(!vis[G[i].from] && !vis[G[i].to] && !check(G[i].from, G[i].to)) {tot--; merge(G[i].from, G[i].to);}
}
ans.emplace(tot);
for(int i = k; i >= 1; i--) {
vis[z[i]] = 0;
tot++;
for(int j = head[z[i]]; j != -1; j = G[j].nxt) {
if(!vis[G[j].to] && !check(G[j].from, G[j].to)) {tot--; merge(G[j].from, G[j].to);}
}
ans.emplace(tot);
}
while(!ans.empty()) {printf("%d\n", ans.top()); ans.pop();}
return 0;
}
正文完