Codeforces292D

题意：

给出n个点和m条无向边，每条无向边依次编号为1～m，给出q次询问，问删去[l,r]这些边后连通分量个数。其中，，。

思路：

并查集是可以用来求无向图连通分量的个数的：

并查集是指比如A和B是一类，A和C是一类，那么A、B、C为一类；

无向图的连通是指比如A和B连通，A和C连通，那么B和肯定也连通，A、B、C就为一个连通分量；

类比一下就知道是怎样操作的了。

删去[l,r]这些边肯定是很难操作的，所以还是考虑添边。

删去[l,r]这些边就相当于添上1～l-1和r+1～m这些边，所以可以想到要用前缀后缀并查集，即保存下每添一条边当时的par情况。

所以对于删掉[l,r]这些边来说，相当于把前l-1条边添好的情况x和后m-r条边添好的情况y来unite一下。

如何unite呢？

因为并查集肯定是在一个数组里面进行操作的，所以先另外开一个数组。先赋初值为x情况，然后遍历每个点，如果发现x情况和y情况点的par不同，就说明这两个par要进行合并，但是这个数组的初值是x情况的，所以要在新数组里把两个par合并，即unite(2,x,find(0,x,i),find(1,y,i)); 。

这样子做的复杂度是O(max(m,q)*n)，并不会爆炸，所以不用tarjan缩点直接做就可以了。

代码：

int n,m;
int eg[10010][2];
int par[3][10010][510];//[0][][]表示前缀
void init(int ps)
{
    int id=0;
    if(ps==1)id=m+1;
    for(int i=1;i<=n;i++)
        par[ps][id][i]=i;
}
int find(int ps,int id,int x)
{
    if(par[ps][id][x]==x)return x;
    return par[ps][id][x]=find(ps,id,par[ps][id][x]);
}
void unite(int ps,int id,int x,int y)
{
    x=find(ps,id,x);y=find(ps,id,y);
    if(x==y)return;
    par[ps][id][x]=y;
}
int psunite(int x,int y)
{
    for(int i=1;i<=n;i++)
        par[2][x][i]=par[0][x][i];
    for(int i=1;i<=n;i++)
        unite(2,x,find(0,x,i),find(1,y,i));
    int ans=0;
    for(int i=1;i<=n;i++)
        if(find(2,x,i)==i)
            ans++;
    return ans;
}
int main()
{
    int q,l,r;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&eg[i][0],&eg[i][1]);
    init(0);
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
            par[0][i][j]=par[0][i-1][j];
        unite(0,i,eg[i][0],eg[i][1]);
    }
    init(1);
    for(int i=m;i>=1;i--)
    {
        for(int j=1;j<=n;j++)
            par[1][i][j]=par[1][i+1][j];
        unite(1,i,eg[i][0],eg[i][1]);
    }
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d%d",&l,&r);
        printf("%d\n",psunite(l-1,r+1));
    }
    return 0;
}
ACM训练联盟周赛D

题意：

求最大的连通分量中的点数，其他同上。

思路：

在上题的基础上每次psunite之后计数每个点的par就可以求出最大的来连通分量中的点数了。

代码：

int n,m;
int eg[10010][2];
int par[3][10010][510];//[0][][]表示前缀
int cnt[10010];
void init(int ps)
{
    int id=0;
    if(ps==1)id=m+1;
    for(int i=1;i<=n;i++)
        par[ps][id][i]=i;
}
int find(int ps,int id,int x)
{
    if(par[ps][id][x]==x)return x;
    return par[ps][id][x]=find(ps,id,par[ps][id][x]);
}
void unite(int ps,int id,int x,int y)
{
    x=find(ps,id,x);y=find(ps,id,y);
    if(x==y)return;
    par[ps][id][x]=y;
}
int psunite(int x,int y)
{
    for(int i=1;i<=n;i++)
        par[2][x][i]=par[0][x][i];
    for(int i=1;i<=n;i++)
        unite(2,x,find(0,x,i),find(1,y,i));
    memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=n;i++)
        cnt[find(2,x,i)]++;
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,cnt[i]);
    return ans;
}
int main()
{
    int q,l,r;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&eg[i][0],&eg[i][1]);
    init(0);
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
            par[0][i][j]=par[0][i-1][j];
        unite(0,i,eg[i][0],eg[i][1]);
    }
    init(1);
    for(int i=m;i>=1;i--)
    {
        for(int j=1;j<=n;j++)
            par[1][i][j]=par[1][i+1][j];
        unite(1,i,eg[i][0],eg[i][1]);
    }
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d%d",&l,&r);
        printf("%d\n",psunite(l-1,r+1));
    }
    return 0;
}