bzoj1015: [JSOI2008]星球大战starwar 并查集+离线处理

2021-07-10 04:04

阅读：334

标签：namespace find add div etc hid ext http jsoi2008

题目传送门

这道题可以改为离线处理倒着找答案这样删点就变成加点了有了这个思想题目就很好写了哇 23333

#include
#include
#include
using namespace std;
const int M=400007;
int read(){
    int ans=0,f=1,c=getchar();
    while(c‘0‘||c>‘9‘){if(c==‘-‘) f=-1; c=getchar();}
    while(c>=‘0‘&&c‘9‘){ans=ans*10+(c-‘0‘); c=getchar();}
    return ans*f;
}
int n,m,k,tot,sum;
int fa[M],ans[M],usd[M],in[M],first[M],q[M];
struct node{int to,next;}e[2*M];
void ins(int a,int b){sum++; e[sum].to=b; e[sum].next=first[a]; first[a]=sum;}
void insert(int a,int b){ins(a,b); ins(b,a);}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void add(int x){
    int p=find(x);
    for(int i=first[x];i;i=e[i].next){
        int now=e[i].to;
        if(usd[now]){
            int q=find(now);
            if(p!=q){fa[q]=p; tot--;}
        }
    }
}
int main()
{
    int x,y;
    n=read(); m=read();
    for(int i=0;ii;
    for(int i=1;iread(),insert(x,y);
    k=read();
    for(int i=1;iin[q[i]]=1;
    for(int i=0;iif(!in[i]){
         tot++;
         add(i);
         usd[i]=1;
    }
    ans[k+1]=tot;
    for(int i=k;i;i--){
        tot++;
        add(q[i]);
        usd[q[i]]=1;
        ans[i]=tot;
    }
    for(int i=1;i1;i++) printf("%d\n",ans[i]);
    return 0;
}

View Code

bzoj1015: [JSOI2008]星球大战starwar 并查集+离线处理

标签：namespace find add div etc hid ext http jsoi2008

原文地址：http://www.cnblogs.com/lyzuikeai/p/7091189.html

上一篇：jquery实现ajax提交表单的方法总结

下一篇：websocket小荔枝

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：bzoj1015: [JSOI2008]星球大战starwar 并查集+离线处理
文章链接：http://soscw.com/index.php/essay/103057.html

亲，登录后才可以留言！

bzoj1015: [JSOI2008]星球大战starwar 并查集+离线处理

评论

热门文章

推荐文章

最新文章

置顶文章