[BZOJ1015/JSOI2008]星球大战

// 此博文为迁移而来，写于2015年7月16日，不代表本人现在的观点与看法。原始地址：http://blog.sina.com.cn/s/blog_6022c4720102w6le.html

 

1、题目

【P.S. BZOJ上的题面问题很多，这里进行了一些修改和简化】

 

2、TAG

       JSOI2008江苏省队选拔题；并查集。

 

3、分析

       作为一道省队选拔题确实感觉有点水水的。可能唯一难点在于难以想到这种方式。由题意，我们先可以想出一种最暴力的做法——对于每次的摧毁，跑一遍DFS判断连通块个数。然而这速度也是极慢的。

       可以这样想：一个星球与其他若干星球相连，则它们必定属于一个连通块；如果将其摧毁，即相当于将所有与其相连的星球拆开，不再属于同一个连通块。但是这样的话，我们难以判断某两个星球它们是不是存在除经过该星球的其他连通路径。

       所以我们可以反过来思考——首先我们将所有要摧毁的星球摧毁，计算出最后时刻的连通块个数，然后我们根据题目所给顺序反着对其进行加点，每一次的添加星球，都是将所有与其相连的星球并入同一个连通块。这样，我们就不需要考虑他们之前的状态了。并入的过程用并查集完成即可。

        

4、代码

---------------------------------------------------------------------------------------------------

#include<cstdio>
#include<cstring>
#define MAXN 400005

 

struct Edge
{
        int v,next,flag;
};
Edge edge[MAXN];

 

int vis[MAXN],now=1,h[MAXN],n,m,v,u,p[MAXN],k,tot,set[MAXN],ans[MAXN],flag[MAXN],del[MAXN];

 

void addEdge(int u,int v)
{
        now++;
        edge[now].v=v;
        edge[now].next=h[u];
        h[u]=now;
}

 

int check(int x)
{
        if (set[x]==x) return x;
        return (set[x]=check(set[x]));
}

 

void DFS(int now,int nowFa)
{
        for (int x=h[now];x!=-1;x=edge[x].next) 
         if (!vis[edge[x].v]) { vis[edge[x].v]=1; set[check(now)]=check(edge[x].v); DFS(edge[x].v,nowFa); }
        return;
}

 

void init()
{
        memset(h,-1,sizeof(h));
        scanf("%d %d",&n,&m);
        for (int i=1;i<=m;i++) 
        {
                scanf("%d %d",&u,&v);
                addEdge(u,v),addEdge(v,u);
        }
        scanf("%d",&k);
        for (int i=1;i<=k;i++) 
        {
                scanf("%d",&p[i]);
                vis[p[i]]=1;
                del[p[i]]=1;
        }
        for (int i=0;i<=n-1;i++) set[i]=i;
        for (int i=0;i<=n-1;i++) if (!vis[i]) { DFS(i,i); tot++; }
}

 

int main()
{
        init();
        int temp=tot;
        for (int i=k;i>=1;i--)
        {
                del[p[i]]=0; tot++;
                for (int x=h[p[i]];x!=-1;x=edge[x].next)
                {   
                        if (del[edge[x].v]) continue;
                        int v1=check(p[i]),v2=check(edge[x].v);
                        if (v1!=v2) { set[v1]=v2; tot--; }
                }
                ans[i]=tot;
        }
        for (int i=1;i<=k;i++) printf("%d ",ans[i]);
        printf("%d",tot);
        return 0;
}
---------------------------------------------------------------------------------------------------