Chlience

【题解】BZOJ 3562 [SHOI2014]神奇化合物
Problem传送门 >ω<题目大意:给定一个图支持删边,加边,询问当前联通块个数Solution估计第一眼看到就...
扫描右侧二维码阅读全文
13
2018/10

【题解】BZOJ 3562 [SHOI2014]神奇化合物

Problem

传送门 >ω<

题目大意:
给定一个图
支持删边,加边,询问当前联通块个数

Solution

估计第一眼看到就想到并查集吧
但是并查集并不资瓷删边

观察到一开始的边可能很多,而操作总数很少,考虑将后面操作不会涉及到的边直接并查集缩端点,然后暴力跑后面的操作

时间复杂度 $O(q^2)$

但是这样会被卡...(虽然说其实好像没卡)

所以我们使用另外一种算法

线段树分治!

如果不知道线段树分治是啥的请转到 【算法】按时间分治的一类算法

同样的,对于后面操作不会涉及到的边直接并查集缩端点
通过时间线段树来维护每条边的影响
然后对线段树进行遍历(DFS)

每个节点从父亲处继承联通块个数,然后与此同时加上这个点上所有的边,计算出联通块个数,并查集维护

那么在 DFS 回溯时如何将操作回退?
首先显然是不能路径压缩的,这样会破坏父子关系

其次加边是按照从上到下的先后顺序,那么假设这条边在加入图中时连接了两个联通块,当其退出时必然会断开两个联通块;若这条边连接的两端属于同一个联通块,那么其退出时两端仍然属于同一个联通块

所以说对于成功连接两个联通块的边直接暴力拆开,没有成功的边不用处理

最后到达叶子节点时处理询问

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5010 , M = 10010;
#define L (x << 1)
#define R (x << 1 | 1)
#define mid ((l + r) >> 1)

struct E {
    int x , y;
    E () {}
    E (int _x , int _y) {x = _x; y = _y;}
};

int n , m , q;
short a[N][N];

E sta[210010];            //保存所有已经放入的边
int top;

char str[10];
int que[M];                //保存询问

int siz[N] , fa[N];        //并查集

int num[M << 2];        //线段树节点联通块数
int head[M << 2] , tot;    //邻接表搞一搞边
E edge[M * 14];            //边最多 q * logq 条
int nxt[M * 14];

bool use[M * 14];        //每条边是否是关键边(能够使得联通块合并/分离)

int ans[M];

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

int findf(int x) {
    while(fa[x] != x) x = fa[x];
    return x;
    //能够“删除”的并查集
}

void addedge(int x , E e) {
    ++ tot;
    edge[tot] = e;
    nxt[tot] = head[x];
    head[x] = tot;
    //邻接表存边
}

void add(int x , int l , int r , int ll , int rr , E e) {
    if(l >= ll  && r <= rr) {addedge(x , e);return;}
    if(mid >= ll) add(L , l , mid , ll , rr , e);
    if(mid < rr) add(R , mid + 1 , r , ll , rr , e);
}

void add_edge(int now) {
    //搜到时加边
    for(int i = head[now] ; i ; i = nxt[i]) {
        int &x = edge[i].x , &y = edge[i].y;
        x = findf(x); y = findf(y);
        if(x == y) continue;
        if(siz[x] < siz[y]) swap(x , y);
        fa[y] = x;
        siz[x] += siz[y];
        use[i] = 1;
        -- num[now];
    } 
}

void del_edge(int now) {
    //回溯时删边
    for(int i = head[now] ; i ; i = nxt[i]) {
        if(!use[i]) continue;
        int &x = edge[i].x , &y = edge[i].y;
        fa[y] = y;
        siz[x] -= siz[y];
    }
}

void dfs(int x , int l , int r) {//对线段树进行遍历
    num[x] = num[x >> 1];
    add_edge(x);
    if(l == r) {
        if(que[l])
            ans[que[l]] = num[x];
    }
    else {
        dfs(L , l , mid);
        dfs(R , mid + 1 , r);
    }
    del_edge(x);
}

int main() {
    n = read() , m = read();
    for(int i = 1 ; i <= m ; ++ i) {
        int x = read() , y = read();
        a[x][y] = a[y][x] = 1;
        sta[++ top] = E(x , y);
    }

    q = read();

    for(int i = 1 ; i <= q ; ++ i) {
        scanf("%s" , str);
        switch(str[0]) {
            case 'A': {
                int x = read() , y = read();
                a[x][y] = a[y][x] = i;
                sta[++ top] = E(x , y);
                break;
            }
            case 'D': {
                int x = read() , y = read();
                add(1 , 1 , q , a[x][y] , i , E(x , y));
                a[x][y] = a[y][x] = 0;
                break;
            }
            case 'Q': {
                que[i] = ++ que[0];
                break;
            }
        }
    }

    for(int i = 1 ; i <= n ; ++ i) {fa[i] = i; siz[i] = 1;}

    for(int i = 1 ; i <= top ; ++ i) {
        int x = sta[i].x , y = sta[i].y;
        if(a[x][y]) {
            if(a[x][y] == 1) {
                int fx = findf(x) , fy = findf(y);
                if(fx == fy) continue;
                if(siz[fx] < siz[fy]) swap(fx , fy);
                fa[fy] = fx; siz[fx] += siz[fy];
            }
            //这里将从头到尾一直没有删除的边直接合并
            else add(1 , 1 , q , a[x][y] , q , E(x , y));
            a[x][y] = a[y][x] = 0;
        }
    }
    for(int i = 1 ; i <= n ; ++ i) if(fa[i] == i) ++ num[0];
    dfs(1 , 1 , q);
    for(int i = 1 ; i <= que[0] ; ++ i)
        printf("%d\n" , ans[i]);
    return 0;
}
Last modification:October 13th, 2018 at 10:49 pm

Leave a Comment