BZOJ3562 [SHOI2014]神奇化合物

2015.03.04 16:19 Wed| 2 visits oi_2015| 2015_刷题日常| Text

Solution

加特技 ——18357

可见边数及其多,询问数及其少。于是我们直接看有哪些边没有被删除过,然后缩点。这样询问数就到了一个可承受的范围之内,暴力即可。

Code

#include <bits/stdc++.h>
using namespace std;
#define N 5005
#define M 200005
#define Q 10005
bitset<N> vis;
int n, m, q, del[N][N], e[N][N], head[N], fa[N], ans;

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

struct $
{
    int x, y;
    $() {}
    $(int _x, int _y) : x(_x), y(_y) {}
} c[M];

struct $$
{
    int o, x, y;
    $$() {}
    $$(int _o, int _x = 0, int _y = 0) : o(_o), x(_x), y(_y) {}
} o[Q];

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to) : next(_next), to(_to) {}
} edge[N << 1];

inline void add(int x, int y)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

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

bool dfs(int x, int y)
{
    if (x == y) return true;
    vis[x] = 1;
    for (int i = head[x]; i; i = edge[i].next)
        if (e[x][edge[i].to] > 0 && !vis[edge[i].to])
            if (dfs(edge[i].to, y)) return true;
    return false;
}

void connect(int x, int y)
{
    vis.reset();
    if (!dfs(x, y)) --ans;
    ++e[x][y]; ++e[y][x];
    add(x, y), add(y, x);
}

void disconnect(int x, int y)
{
    vis.reset();
    --e[x][y]; --e[y][x];
    if (!dfs(x, y)) ++ans;
}

int main()
{
    cin >> n >> m;
    for (int x, y, i = 1; i <= m; ++i)
        x = read(), y = read(), c[i] = $(x, y);
    cin >> q;
    char str[5];
    for (int i = 1; i <= q; ++i)
    {
        scanf("%s", str);
        if (str[0] == 'Q') { o[i] = $$(3); continue; }
        int x = read(), y = read();
        if (str[0] == 'A')
            o[i] = $$(1, x, y);
        else
            o[i] = $$(2, x, y), del[x][y] = del[y][x] = 1;
    }
    for (int i = 1; i <= n; ++i)
        fa[i] = i;
    for (int i = 1; i <= m; ++i)
        if (!del[c[i].x][c[i].y] && find(c[i].x) != find(c[i].y))
            fa[fa[c[i].y]] = fa[c[i].x];
    for (int i = 1; i <= n; ++i)
    {
        find(i);
        if (i == fa[i]) ++ans;
    }
    for (int i = 1; i <= m; ++i)
        if (fa[c[i].x] != fa[c[i].y])
            connect(fa[c[i].x], fa[c[i].y]);
    for (int i = 1; i <= q; ++i)
    {
        if (o[i].o == 1) connect(fa[o[i].x], fa[o[i].y]);
        if (o[i].o == 2) disconnect(fa[o[i].x], fa[o[i].y]);
        if (o[i].o == 3) printf("%d\n", ans);
    }
}