并查集
正序处理时间复杂度为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的更多相关文章
-
BZOJ1015[JSOI2008]星球大战starwar[并查集]
1015: [JSOI2008]星球大战starwar Time Limit: 3 Sec Memory Limit: 162 MBSubmit: 5253 Solved: 2395[Submit ...
-
bzoj1015:1015: [JSOI2008]星球大战starwar
应该是全部读入之后再添加边用并查集就可以了. yyl用空间换时间.u[]v[]等将边预存起来. #include<cstdio> #include<cstring> #incl ...
-
BZOJ1015 [JSOI2008]星球大战starwar(并查集)
1015: [JSOI2008]星球大战starwar Time Limit: 3 Sec Memory Limit: 162 MBSubmit: 3895 Solved: 1750[Submit ...
-
[Bzoj1015][JSOI2008]星球大战starwar(并查集)(离线处理)
1015: [JSOI2008]星球大战starwar Time Limit: 3 Sec Memory Limit: 162 MBSubmit: 6849 Solved: 3204[Submit ...
-
1015: [JSOI2008]星球大战starwar
1015: [JSOI2008]星球大战starwar Time Limit: 3 Sec Memory Limit: 162 MB Description 很久以前,在一个遥远的星系,一个黑暗的帝国 ...
-
[1015][JSOI2008]星球大战starwar(并查集)
1015: [JSOI2008]星球大战starwar Time Limit: 3 Sec Memory Limit: 162 MBSubmit: 2124 Solved: 909[Submit] ...
-
BZOJ 1015: [JSOI2008]星球大战starwar 并查集
1015: [JSOI2008]星球大战starwar Description 很久以前,在一个遥远的星系,一个黑暗的帝国靠着它的超级武器统治者整个星系.某一天,凭着一个偶然的机遇,一支反抗军摧毁了帝 ...
-
【BZOJ】1015: [JSOI2008]星球大战starwar
1015: [JSOI2008]星球大战starwar 题意:一个点数为N(1<= 40w),边数为M(1<=20w)的图,总共删除k个节点,问开始以及每次删除一个节点之后图的连通块数? ...
-
BZOJ 1015 [JSOI2008]星球大战starwar
1015: [JSOI2008]星球大战starwar Time Limit: 3 Sec Memory Limit: 162 MBSubmit: 3551 Solved: 1581[Submit ...
随机推荐
-
AB窗体互传参数
一.找了好几个,都不靠谱,不是说不靠谱,自己感觉太繁琐 二.父窗口传子窗口好传,有两种方法(自己认为比较简单的方法哈), 1第一种方法:在子窗口中新建一个属性:再新建一个方法,当然方法就是把属性个窗体 ...
-
momentjs 求小时差异
momentjs 使用 var now1 = moment( moment().unix()*1000); //获取unix时间戳 需要*1000 var befor_time = moment(1 ...
-
【转载】Erlang 中 link 和 monitor 的区别
Link and Monitor differences 原文地址 Introduction link/1 and monitor/2 are 2 different ways of notifyin ...
-
Android横竖屏切换继续播放视频
只需要重新onSaveInstanceState方法,在其里面记住我们要记录的参数 package com.bawei.day07_videoview; import android.os.Bundl ...
-
cocos2dx 菜单按钮回调方法传参 tag传参
.h文件 void menuCallBack(CCObject* pSender); .cpp CCMenuItemSprite* item = CCMenuItemSprite::create( m ...
-
MongoDB Query
每条数据格式如下 { "_id" : ObjectId("5383298561aa33a422d8603e"), "day" : " ...
-
bzoj 4538: [Hnoi2016]网络
Description 一个简单的网络系统可以被描述成一棵无根树.每个节点为一个服务器.连接服务器与服务器的数据线则看做一条树边.两个服务器进行数据的交互时,数据会经过连接这两个服务器的路径上的所有服 ...
-
Storm 对 0.10.x 版 Kafka之commit offsets
由于 0.10.x 版 Kafka 与 0.8.x 版有很大的变化,这种变化对下游 Storm 有非常大的影响,0.10.x 版的 Kafka 不但增加了权限管理的功能,而且还将 simple 和 h ...
-
CRT-常用命令
1 目录操作 mkdir a ;(新建文件夹) mkdir -p a/b;(新建多及目录文件夹) Rmdir a (a只能是空目录) Rmdir -p a (a可以是多级目录) 2 文件操作 touc ...
-
jvm常用参数
-Xms512m:初始堆内存 -Xmx512m:最大堆内存 -XX:PermSize=256m:初始永久代内存(方法区,非堆) -XX:MaxPermSize=256m:最大永久代内存(方法区,非堆) ...