2017.07.08【NOIP向上組】模擬試合B組連通ブロック(connect)問題解

原題:
http://172.16.0.132/senior/#contest/show/2041/1
タイトルの説明:
無方向図の連通ブロックの数を知っておくべきで、連通ブロックの数を求める方法を知っておくべきです.あなたが興奮してあなたの成果と、破壊王アリスは図の中の辺を分解しました.彼女が発見すると、エッジを削除するたびに、エッジの番号をメモし、現在の連通ブロックの数を教えます.しかし、エッジ番号は悲劇的です.Aliceはあなたをいじめるために、lからrまでのエッジ番号を取り外します.もちろん、連通ブロックの個数を求める必要があります.もしあなたが答えたら、Aliceは取り外した辺を詰めて、次の破壊をします.もしあなたがこの任務を完成できないならば、Aliceは徹底的にあなたの図を破壊します.何度もやった後、Aliceは退屈で、遊びに行きましたが、あなたは3番目の問題を続けなければなりません.
入力:
1行目の2つの整数n,mは、点数と辺数を表す.その後、m行の各行の2つの整数x,yは、xとyの間にエッジがあるかどうかを表す.(読み込み順にエッジ番号を付け、番号は1から)1行に1つの整数kを与え、Aliceの破壊回数を表す.その後k行、1行あたり2つの整数l,r.
出力:
k行、各行に1つの整数.
サンプル入力:
6 5 1 2 5 4 2 3 3 1 3 6 6 1 3 2 5 1 5 5 5 2 4 3 3
サンプル出力:
4 5 6 3 4 2
データ範囲の制限:
30%のデータに対して、n<=100、k<=10は60%のデータに対して、k<=1000は100%のデータに対して、n<=500、m<=10000、k<=200000、1<=l<=r<=m
分析:
そして、セットを調べてF[i]配列を設定して、前のi辺のみを追加したときのすべてのノードの接続状況を記録してもいいです.もう1つのG[i]配列を設定し,i-mエッジのみを追加した場合のすべてのノードの連通を記録する.質問ごとにF[l-1],G[r+1]をマージすればよい.
実装:

#include
#include
#include
using namespace std;

int x,y,ans,k,xx,yy,n,m,i,f[10001][501],g[10001][501],mg[501],mk[501],a[10001][3];
int getf(int x,int i){return f[i][x]==x?x:(f[i][x]=getf(f[i][x],i));}
int getg(int x,int i){return g[i][x]==x?x:(g[i][x]=getg(g[i][x],i));}
int get(int x){ return mg[x]==x?x:(mg[x]=get(mg[x]));}
int main()
{
    freopen("connect.in","r",stdin);freopen("connect.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++) scanf("%d%d",&a[i][1],&a[i][2]);
    for(i=1;i<=n;i++) f[0][i]=i,g[m+1][i]=i;
    for(i=1;i<=m;i++)
    {
        memcpy(f[i],f[i-1],sizeof(f[i]));
        xx=getf(a[i][1],i);
        yy=getf(a[i][2],i);
        if(xx!=yy) f[i][xx]=yy;    
    }
    for(i=m;i>=1;i--)
    {
        memcpy(g[i],g[i+1],sizeof(g[i]));
        xx=getg(a[i][1],i);
        yy=getg(a[i][2],i);
        if(xx!=yy) g[i][xx]=yy;
    }   
    scanf("%d",&k);
    while (k--)
    {
        scanf("%d%d",&x,&y);
        if(x>y) swap(x,y);
        ans=0;
        memcpy(mg,f[x-1],sizeof(mg));
        for(i=1;i<=n;i++)
        {
            xx=get(mg[i]);
            yy=get(g[y+1][i]);
            if(xx!=yy) mg[xx]=yy;   
        }
        for(i=1;i<=n;i++)
        {
            xx=get(mg[i]);
            if(mk[xx]!=k) mk[xx]=k,ans++;
        }
        printf("%d
",ans);
    }
}