P1197 [JSOI2008]星球大战并查集反向

题目描述

很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治着整个星系。

某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。

但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始不可靠起来。

现在，反抗军首领交给你一个任务：给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序，以尽量快的速度求出每一次打击之后反抗军占据的星球的连通块的个数。（如果两个星球可以通过现存的以太通道直接或间接地连通，则这两个星球在同一个连通块中）。

输入输出格式

输入格式：

输入文件第一行包含两个整数，

接下来的

接下来的一行为一个整数

接下来的

输出格式：

第一行是开始时星球的连通块个数。接下来的

输入输出样例

输入样例#1：复制

输出样例#1：复制

1
1
1
2
3
3
题意： 给n个点（0-n-1）   然后给出m条无向边  每次去掉一个点（该点连接的路自然也断了）

是光笔农场进一步

一开始写了一个最小生成树  最小生成树具有判断联通块的作用  
但是只过了两个点  数据2e5 比较大   加上每次都重现最小生成树没有本质上的优化速度 和暴力一样

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);i--)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define LL long long
#define pb push_back
#define fi first
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
///////////////////////////////////
#define inf 0x3f3f3f3f
#define N 200000+5
int f[N];
int vis[N];
int find1(int x)
{
    return f[x]==x?x:find1(f[x]);
}
int n,m;
struct node
{
    int s,e;
}edge[N];

int kruskal()
{
    int x=1;
    rep(i,0,n)
    f[i]=i;
    rep(i,1,m)
    {
        int a=find1(edge[i].s);
        int b=find1(edge[i].e);
        if(a==b)continue;
        if(vis[ edge[i].s ]||vis[ edge[i].e ])continue;
        x++;
        f[a]=b;
    }
    return x;
}

int main()
{
    RII(n,m);
    rep(i,1,m)
    {
        RII(edge[i].s,edge[i].e);
    }
    printf("%d
",n-kruskal()+1);
    int q;
    int t=n;
    RI(q);
    while(q--)
    {
        int x;
        RI(x);
        vis[x]=1;
        t--;
        int ans=kruskal();
        printf("%d
",t-ans+1);
    }
    return 0;
}

View Code


反向并查集  
ans[k+1]等于  一开始 （也就是除了被打破的星球剩下的星球的联通图）  
然后i倒叙遍历被打破的点
每次遍历 连通图先加1  因为加入了一个独立的点  然后遍历和这个点有关的所有边  如果另一点是没被打破的 且与该独立点不连通  将其联通 并且ans--；
直到修复到1位置  那么就是正序的原始图了（也就是没有任何一个点被打破的图）
注意实现查找与这个点有关的边链表方法

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);i--)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define LL long long
#define pb push_back
#define fi first
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
///////////////////////////////////
#define inf 0x3f3f3f3f
#define N 400000+5
int f[N];
struct node
{
    int s,e,next;
}s[N];
int find1(int x)
{
    return f[x]==x?x:f[x]=find1(f[x]);
}
void union1(int a,int b)
{
    int x=find1(a);
    int y=find1(b);
    if(x!=y)f[x]=y;
}
int head[N];
int broken[N];
int node[N];
int ans[N];
int cnt=0;
void add(int u,int v)//主要为了更加方便的遍历它的边
{
    s[++cnt].s=u;

    s[cnt].next=head[u];//往回指
    head[u]=cnt;
    s[cnt].e=v;
}
int main()
{
    int n,m;
    RII(n,m);
    rep(i,0,n)
    f[i]=i,head[i]=-1;//一定要初始化-1

    while(m--)
    {
        int a,b;
        RII(a,b);
        add(a,b);
        add(b,a);
    }
    int q;
    RI(q);
    rep(i,1,q)
    {
        RI(node[i]);
        broken[node[i]]=1;//已经被破坏
    }
    int sum=n-q;
    rep(i,1,cnt)//先遍历一遍原始图  也就是除了被打破的星球的图
    if(!broken[ s[i].s ]&&!broken[ s[i].e ]&&find1(s[i].s)!=find1(s[i].e))
    {
        sum--;
        union1(s[i].s,s[i].e);
    }
    ans[q+1]=sum;
    repp(i,q,1)
    {
        sum++;//每修复一个星球  联通块加一 因为一开始他是独立的
        broken[ node[i] ]=0;
        for(int j=head[node[i]];j!=-1;j=s[j].next )
        {
            if(!broken[s[j].e]&&find1(s[j].e)!=find1(node[i]) )
            {
                sum--;union1(s[j].e,node[i]);
            }
        }
        ans[i]=sum;
    }
    rep(i,1,q+1)
    printf("%d
",ans[i]);
   return 0;

}

View Code

P1197 [JSOI2008]星球大战 并查集 反向

题目描述

输入输出格式

输入输出样例

P1197 [JSOI2008]星球大战并查集反向