题目描述

你应该知道无向图的连通块的数量，你应该知道如何求连通块的数量。当你兴奋与你的成就时，破坏王Alice拆掉了图中的边。当她发现，每删去一条边，你都会记下边的编号，同时告诉她当前连通块的个数。

然而，对边编号简直就是个悲剧，因为Alice为了刁难你，拆掉编号从l到r的边，当然你需要做的事情就是求连通块的个数。如果你答对了，Alice会把拆掉的边装好，迚行下一次破坏。如果你无法完成这个任务，Alice会彻底毁了你的图。

进行完足够多次之后，Alice觉得无聊，就玩去了，而你却需要继续做第三题。

思路

两个并查集，f[i]表示前i条边所连成的点的集合，g[j]表示后j条边所连成的点的集合。 那么对于一个询问 [l,r]，我们就可以通过合并f[l-1]和g[r+1]两个集合来确定有几个联通块

#include 
#include 
using namespace std;
int n, m;
#define fill(x, y) memset(x, y, sizeof(x))
int f[10005][501], g[10005][501], a[10001][3], fl[501];
__attribute__((optimize("-O2")))
inline int find(int x, int t)
{
    //if (t > m || t < 1) return 0;
    if (!f[t][x]) return x;
    f[t][x] = find(f[t][x], t);
    return f[t][x];
}
__attribute__((optimize("-O2")))
inline int insert(int x, int y, int t)
{
    if (find(x, t) != find(y, t))
    {
        f[t][find(x, t)] = find(y, t);
        return 0;
    }
    return 0;
}
__attribute__((optimize("-O2")))
inline int find1(int x, int t)
{
    //if (t > m || t < 1) return 0;
    if (!g[t][x]) return x;
    g[t][x] = find1(g[t][x], t);
    return g[t][x];
}
__attribute__((optimize("-O2")))
inline int insert1(int x, int y, int t)
{
    //int xx = find1(x, t), yy = find1(y, t);
    if (find1(x, t) != find1(y, t))
    {
        g[t][find1(x, t)] = find1(y, t);
        return 0;
    }
    return 0;
}
__attribute__((optimize("-O2")))
inline int find2(int x)
{
    if (!fl[x]) return x;
    fl[x] = find2(fl[x]);
    return fl[x];
}
__attribute__((optimize("-O2")))
inline int insert2(int x, int y, int r)
{
    int xx = find2(x), yy = find2(y);
    if (xx != yy)
    {
        fl[xx] = yy;
        return 0;
    }
    return 0;
}
int main()
{
    freopen("connect.in","r",stdin);
    freopen("connect.out","w",stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        a[i][1] = x; a[i][2] = y;
        for (int j = 1; j <= n; j++)
        {
            f[i][j] = f[i - 1][j];
        }
        insert(x, y, i);
    }
    for (int i = m; i >= 1; i--)
    {
        int x = a[i][1], y = a[i][2];
        for (int j = 1; j <= n; j++)
        {
            g[i][j] = g[i + 1][j];
        }
        insert1(x, y, i);
    }
    int t;
    scanf("%d", &t);
    for (int i = 1; i <= t; i++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        int ans = 0;
        for (int j = 1; j <= n; j++)
            fl[j] = f[l - 1][j];
        for (int j = 1; j <= n; j++)
        {
            if (find2(j) != find1(j , r + 1))
            {
                insert2(find2(j), find1(j ,r + 1), r + 1);
            }   
        }
        for (int j = 1; j <= n; j++)
            if (fl[j] == 0) ans++;
        printf("%d\n", ans);
    }
}