D. Connected Components

https://www.codeforces.com/contest/292/problem/D

思路

由于需要删除任意 连续段的 连接线，

引入前缀和

连续段的左右两边都需要，

所以引入两个前缀和。

https://blog.csdn.net/qq_28954601/article/details/79281640

Code

https://blog.csdn.net/qq_28954601/article/details/79281640

#include<bits/stdc++.h>
#define IO ios::sync_with_stdio(false);\
    cin.tie(0);\
    cout.tie(0);
using namespace std;
const int maxn = 510;
const int maxm = 1e4+10;

struct node
{
    int fa[maxn],Bcnt;
    int find_set(int x)
    {
        if(fa[x]!=x)
            fa[x] = find_set(fa[x]);
        return fa[x];
    }
    void union_set(int x,int y)
    {
        x = find_set(x);
        y = find_set(y);
        if(x==y)
            return;
        fa[y] = x;
        ++Bcnt;
    }
    node()
    {
        for(int i=1; i<maxn; i++)
            fa[i] = i;
    }
} L[maxm],R[maxm];

int n,m,q;
int x[maxm],y[maxm];

int main()
{
    IO;
    cin>>n>>m;
    for(int i=1; i<=m; i++)
        cin>>x[i]>>y[i];
    for(int i=1; i<=m; i++)
    {
        L[i] = L[i-1];
        L[i].union_set(x[i],y[i]);
    }
    for(int i=m; i>=1; i--)
    {
        R[i] = R[i+1];
        R[i].union_set(x[i],y[i]);
    }
    cin>>q;
    while(q--)
    {
        int u,v;
        cin>>u>>v;
        node ans = L[u-1];
        for(int i=1; i<=n; i++)
            ans.union_set(ans.find_set(i),R[v+1].find_set(i));
        cout<<n-ans.Bcnt<<endl;
    }
    return 0;
}

https://mirror.codeforces.com/contest/292/submission/202137917