[JSOI2008]星球大战starwar BZOJ1015

时间:2022-02-06 01:38:15

并查集

正序处理时间复杂度为n^2,考虑逆序处理,这样,时间复杂度从n^2降为nlogn

附上代码:

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <queue>
using namespace std;
#define N 400005
int fa[N<<1],n,m,K,head[N<<1],cnt,q[N],ans[N];
struct node
{
int to,next;
}e[N<<1];
void add(int x,int y)
{
e[cnt].to=y;
e[cnt].next=head[x];
head[x]=cnt++;
return ;
}
int find(int x)
{
int p=x,t;
while(fa[p]!=p)p=fa[p];
while(x!=p)t=fa[x],fa[x]=p,x=t;
return p;
}
bool vis[N];
int main()
{
for(int i=1;i<N;i++)fa[i]=i;
memset(head,-1,sizeof(head));
memset(vis,1,sizeof(vis));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
x++,y++;
add(x,y);
add(y,x);
}
scanf("%d",&K);
ans[K]=n-K;
for(int i=1;i<=K;i++)
{
scanf("%d",&q[i]);
q[i]++;
vis[q[i]]=0;
}
for(int i=1;i<=n;i++)
{
if(!vis[i])continue;
for(int j=head[i];j!=-1;j=e[j].next)
{
int to1=e[j].to;
if(!vis[to1])continue;
int fx=find(i),fy=find(to1);
if(fx!=fy)
{
fa[fx]=fy;
ans[K]--;
}
}
}
vis[q[K]]=1;
for(int i=K-1;i>=0;i--)
{
ans[i]=ans[i+1]+1;
for(int j=head[q[i+1]];j!=-1;j=e[j].next)
{
int to1=e[j].to;
if(!vis[to1])continue;
int fx=find(q[i+1]),fy=find(to1);
if(fx!=fy)
{
fa[fx]=fy;
ans[i]--;
}
}
vis[q[i]]=1;
}
for(int i=0;i<=K;i++)
{
printf("%d\n",ans[i]);
}
return 0;
}

  

[JSOI2008]星球大战starwar BZOJ1015的更多相关文章

  1. BZOJ1015&lbrack;JSOI2008&rsqb;星球大战starwar&lbrack;并查集&rsqb;

    1015: [JSOI2008]星球大战starwar Time Limit: 3 Sec  Memory Limit: 162 MBSubmit: 5253  Solved: 2395[Submit ...

  2. bzoj1015:1015&colon; &lbrack;JSOI2008&rsqb;星球大战starwar

    应该是全部读入之后再添加边用并查集就可以了. yyl用空间换时间.u[]v[]等将边预存起来. #include<cstdio> #include<cstring> #incl ...

  3. BZOJ1015 &lbrack;JSOI2008&rsqb;星球大战starwar(并查集)

    1015: [JSOI2008]星球大战starwar Time Limit: 3 Sec  Memory Limit: 162 MBSubmit: 3895  Solved: 1750[Submit ...

  4. &lbrack;Bzoj1015&rsqb;&lbrack;JSOI2008&rsqb;星球大战starwar(并查集)(离线处理)

    1015: [JSOI2008]星球大战starwar Time Limit: 3 Sec  Memory Limit: 162 MBSubmit: 6849  Solved: 3204[Submit ...

  5. 1015&colon; &lbrack;JSOI2008&rsqb;星球大战starwar

    1015: [JSOI2008]星球大战starwar Time Limit: 3 Sec Memory Limit: 162 MB Description 很久以前,在一个遥远的星系,一个黑暗的帝国 ...

  6. &lbrack;1015&rsqb;&lbrack;JSOI2008&rsqb;星球大战starwar(并查集)

    1015: [JSOI2008]星球大战starwar Time Limit: 3 Sec  Memory Limit: 162 MBSubmit: 2124  Solved: 909[Submit] ...

  7. BZOJ 1015&colon; &lbrack;JSOI2008&rsqb;星球大战starwar 并查集

    1015: [JSOI2008]星球大战starwar Description 很久以前,在一个遥远的星系,一个黑暗的帝国靠着它的超级武器统治者整个星系.某一天,凭着一个偶然的机遇,一支反抗军摧毁了帝 ...

  8. 【BZOJ】1015&colon; &lbrack;JSOI2008&rsqb;星球大战starwar

    1015: [JSOI2008]星球大战starwar 题意:一个点数为N(1<= 40w),边数为M(1<=20w)的图,总共删除k个节点,问开始以及每次删除一个节点之后图的连通块数? ...

  9. BZOJ 1015 &lbrack;JSOI2008&rsqb;星球大战starwar

    1015: [JSOI2008]星球大战starwar Time Limit: 3 Sec  Memory Limit: 162 MBSubmit: 3551  Solved: 1581[Submit ...

随机推荐

  1. AB窗体互传参数

    一.找了好几个,都不靠谱,不是说不靠谱,自己感觉太繁琐 二.父窗口传子窗口好传,有两种方法(自己认为比较简单的方法哈), 1第一种方法:在子窗口中新建一个属性:再新建一个方法,当然方法就是把属性个窗体 ...

  2. momentjs 求小时差异

    momentjs  使用 var now1 = moment( moment().unix()*1000); //获取unix时间戳 需要*1000 var befor_time = moment(1 ...

  3. 【转载】Erlang 中 link 和 monitor 的区别

    Link and Monitor differences 原文地址 Introduction link/1 and monitor/2 are 2 different ways of notifyin ...

  4. Android横竖屏切换继续播放视频

    只需要重新onSaveInstanceState方法,在其里面记住我们要记录的参数 package com.bawei.day07_videoview; import android.os.Bundl ...

  5. cocos2dx 菜单按钮回调方法传参 tag传参

    .h文件 void menuCallBack(CCObject* pSender); .cpp CCMenuItemSprite* item = CCMenuItemSprite::create( m ...

  6. MongoDB Query

    每条数据格式如下 { "_id" : ObjectId("5383298561aa33a422d8603e"), "day" : &quot ...

  7. bzoj 4538&colon; &lbrack;Hnoi2016&rsqb;网络

    Description 一个简单的网络系统可以被描述成一棵无根树.每个节点为一个服务器.连接服务器与服务器的数据线则看做一条树边.两个服务器进行数据的交互时,数据会经过连接这两个服务器的路径上的所有服 ...

  8. Storm 对 0&period;10&period;x 版 Kafka之commit offsets

    由于 0.10.x 版 Kafka 与 0.8.x 版有很大的变化,这种变化对下游 Storm 有非常大的影响,0.10.x 版的 Kafka 不但增加了权限管理的功能,而且还将 simple 和 h ...

  9. CRT-常用命令

    1 目录操作 mkdir a ;(新建文件夹) mkdir -p a/b;(新建多及目录文件夹) Rmdir a (a只能是空目录) Rmdir -p a (a可以是多级目录) 2 文件操作 touc ...

  10. jvm常用参数

    -Xms512m:初始堆内存 -Xmx512m:最大堆内存 -XX:PermSize=256m:初始永久代内存(方法区,非堆) -XX:MaxPermSize=256m:最大永久代内存(方法区,非堆) ...