URAL 1671 Anansi's Cobweb （并查集）

浏览数：18 / 时间：2015年06月09日

题意：给一个无向图。每次查询破坏一条边，每次输出查询后连通图的个数。

思路：并查集。逆向思维，删边变成加边。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iostream>
#define inf -100000000
#define LL long long
#define maxn 100005
using namespace std;
struct Edge
{
    int x,y;
};
int parent[maxn];
int findset(int p)
{
    return (parent[p]==p)?p:(parent[p]=findset(parent[p]));
}
Edge edge[maxn];
int query[maxn];
bool build[maxn];
int ans[maxn];
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(build,0,sizeof(build));
        for(int i=1; i<=m; ++i)
            scanf("%d%d",&edge[i].x,&edge[i].y);
        int q;
        scanf("%d",&q);
        for(int i=1; i<=q; ++i)
        {
            scanf("%d",&query[i]);
            build[query[i]]=true;
        }
        for(int i=1; i<=n; ++i)
            parent[i]=i;
        int cnt=0;
        for(int i=1; i<=m; ++i)
            if(!build[i])
            {
                int fa=findset(edge[i].x),fb=findset(edge[i].y);
                if(fa!=fb)
                    parent[fa]=fb;
            }
        for(int i=1; i<=n; ++i)
            if(findset(i)==i) cnt++;
        for(int i=q; i>=1; --i)
        {
            ans[i]=cnt;
            int fa=findset(edge[query[i]].x),fb=findset(edge[query[i]].y);
            if(fa!=fb)
            {
                parent[fa]=fb;
                cnt--;
            }
        }
        for(int i=1; i<=q; ++i)
            if(i==1) printf("%d",ans[i]);
            else printf(" %d",ans[i]);
        printf("\n");
    }
    return 0;
}