专栏首页数据结构与算法P1197 [JSOI2008]星球大战

P1197 [JSOI2008]星球大战

题目描述

很久以前,在一个遥远的星系,一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天,凭着一个偶然的机遇,一支反抗军摧毁了帝国的超级武器,并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。

但好景不长,很快帝国又重新造出了他的超级武器。凭借这超级武器的力量,帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁,两个星球之间的通讯通道也开始不可靠起来。现在,反抗军首领交给你一个任务:给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序,以尽量快的速度求出每一次打击之后反抗军占据的星球的连通快的个数。(如果两个星球可以通过现存的以太通道直接或间接地连通,则这两个星球在同一个连通块中)。

输入输出格式

输入格式:

输入文件第一行包含两个整数,N (1 <= N <= 2M) 和M (1 <= M <= 200,000),分别表示星球的数目和以太隧道的数目。星球用0~N-1的整数编号。

接下来的M行,每行包括两个整数X, Y,其中(0<=X<>Y<N),表示星球X和星球Y之间有以太隧道。注意所有的以太隧道都是双向的。

接下来一行是一个整数K,表示帝国计划打击的星球个数。

接下来的K行每行一个整数X,满足0<=X<N,表示帝国计划打击的星球编号。帝国总是按输入的顺序依次摧毁星球的。

输出格式:

输出文件的第一行是开始时星球的连通块个数。

接下来的K行,每行一个整数,表示经过该次打击后现存星球的连通块个数。

输入输出样例

输入样例#1:

8 13
0 1
1 6
6 5
5 0
0 6
1 2
2 3
3 4
4 5
7 1
7 2
7 6
3 6
5
1
6
3
5
7

输出样例#1:

1
1
1
2
3
3

说明

[JSOI2008]

并查集的倒序使用,

一开始假设所有的星球全部摧毁

然后离线处理

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 using namespace std;
  6 void read(int & n)
  7 {
  8     char c='+';int x=0;
  9     while(c<'0'||c>'9')
 10     c=getchar();
 11     while(c>='0'&&c<='9')
 12     {
 13         x=x*10+(c-48);
 14         c=getchar();
 15     }
 16     n=x;
 17 }
 18 const int MAXN=400001;
 19 struct node
 20 {
 21     int u,v,nxt;
 22 }edge[MAXN];
 23 int head[MAXN];
 24 int num=1;
 25 int fa[MAXN];
 26 int n,m,t;
 27 void add_edge(int x,int y)
 28 {
 29     edge[num].u=x;
 30     edge[num].v=y;
 31     edge[num].nxt=head[x];
 32     head[x]=num++;
 33 }
 34 int vis[MAXN];
 35 int des[MAXN];
 36 int ans[MAXN];
 37 int find(int x)
 38 {
 39     if(fa[x]==x)
 40     return fa[x];
 41     else
 42     return fa[x]=find(fa[x]);
 43 }
 44 void unionn(int x,int y)
 45 {
 46     int fx=find(x);
 47     int fy=find(y);
 48     fa[fx]=fy;
 49 }
 50 int create(int p)
 51 {
 52     vis[p]=0;
 53     int x=0;
 54     for(int i=head[p];i!=-1;i=edge[i].nxt)
 55     {
 56         if(vis[edge[i].v]==0&&find(edge[i].u)!=find(edge[i].v))
 57         {
 58             unionn(edge[i].u,edge[i].v);
 59             x++;
 60         }
 61     }
 62     return x;
 63     
 64 }
 65 int vis2[MAXN];
 66 int calc()
 67 {
 68     memset(vis2,0,sizeof(vis2));
 69     int tot=0;
 70     for(int i=0;i<n;i++)
 71     {
 72         if(vis[i]==0&&find(i)==i)
 73         {
 74             //vis2[fa[i]]=1;
 75             tot++;
 76         }
 77     }
 78     return tot;
 79 }
 80 int main()
 81 {
 82     freopen("bzoj_1015.in","r",stdin);
 83     freopen("bzoj_1015.out","w",stdout);
 84     read(n);read(m);
 85     for(int i=0;i<n;i++)
 86         head[i]=-1,fa[i]=i;
 87     for(int i=0;i<m;i++)
 88     {
 89         int x,y;
 90         read(x);read(y);
 91         add_edge(x,y);add_edge(y,x);
 92     }
 93     read(t);
 94     for(int i=0;i<t;i++)
 95     {
 96         read(des[i]);
 97         vis[des[i]]=1;
 98     }
 99     for(int i=0;i<n;i++)
100     {
101         for(int j=head[i];j!=-1;j=edge[j].nxt)
102         if(vis[edge[j].u]==0&&vis[edge[j].v]==0)
103                 unionn(edge[j].u,edge[j].v);
104     }
105     ans[t]=calc();
106     for(int i=t-1;i>=0;i--)
107     {
108         int num=create(des[i]);
109         ans[i]=calc();
110     }
111     for(int i=0;i<=t;i++)
112     {
113         printf("%d\n",ans[i]);
114     }
115     return 0;
116 }
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 using namespace std;
  6 void read(int & n)
  7 {
  8     char c='+';int x=0;
  9     while(c<'0'||c>'9')
 10     c=getchar();
 11     while(c>='0'&&c<='9')
 12     {
 13         x=x*10+(c-48);
 14         c=getchar();
 15     }
 16     n=x;
 17 }
 18 const int MAXN=400001;
 19 struct node
 20 {
 21     int u,v,nxt;
 22 }edge[MAXN];
 23 int head[MAXN];
 24 int num=1;
 25 int fa[MAXN];
 26 int n,m,t;
 27 void add_edge(int x,int y)
 28 {
 29     edge[num].u=x;
 30     edge[num].v=y;
 31     edge[num].nxt=head[x];
 32     head[x]=num++;
 33 }
 34 int vis[MAXN];
 35 int des[MAXN];
 36 int ans[MAXN];
 37 int find(int x)
 38 {
 39     if(fa[x]==x)
 40     return fa[x];
 41     else
 42     return fa[x]=find(fa[x]);
 43 }
 44 void unionn(int x,int y)
 45 {
 46     int fx=find(x);
 47     int fy=find(y);
 48     fa[fx]=fy;
 49 }
 50 int create(int p)
 51 {
 52     vis[p]=0;
 53     int x=0;
 54     for(int i=head[p];i!=-1;i=edge[i].nxt)
 55     {
 56         if(vis[edge[i].v]==0&&find(edge[i].u)!=find(edge[i].v))
 57         {
 58             unionn(edge[i].u,edge[i].v);
 59             x++;
 60         }
 61     }
 62     return x;
 63     
 64 }
 65 int vis2[MAXN];
 66 int calc()
 67 {
 68     memset(vis2,0,sizeof(vis2));
 69     int tot=0;
 70     for(int i=0;i<n;i++)
 71     {
 72         if(vis[i]==0&&find(i)==i)
 73         {
 74             //vis2[fa[i]]=1;
 75             tot++;
 76         }
 77     }
 78     return tot;
 79 }
 80 int main()
 81 {
 82     freopen("bzoj_1015.in","r",stdin);
 83     freopen("bzoj_1015.out","w",stdout);
 84     read(n);read(m);
 85     for(int i=0;i<n;i++)
 86         head[i]=-1,fa[i]=i;
 87     for(int i=0;i<m;i++)
 88     {
 89         int x,y;
 90         read(x);read(y);
 91         add_edge(x,y);add_edge(y,x);
 92     }
 93     read(t);
 94     for(int i=0;i<t;i++)
 95     {
 96         read(des[i]);
 97         vis[des[i]]=1;
 98     }
 99     for(int i=0;i<n;i++)
100     {
101         for(int j=head[i];j!=-1;j=edge[j].nxt)
102         if(vis[edge[j].u]==0&&vis[edge[j].v]==0)
103                 unionn(edge[j].u,edge[j].v);
104     }
105     ans[t]=calc();
106     for(int i=t-1;i>=0;i--)
107     {
108         int num=create(des[i]);
109         ans[i]=ans[i+1]-num+1;
110     }
111     for(int i=0;i<=t;i++)
112     {
113         printf("%d\n",ans[i]);
114     }
115     return 0;
116 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 洛谷P3763 [TJOI2017]DNA(后缀数组 RMQ)

    具体来说,每次比较当前后缀和\(S_0\)的lcp,如果长度\(< N\)的话就从不合法的位置继续匹配

    attack
  • BZOJ5249: [2018多省省队联测]IIIDX(线段树 贪心)

    不难发现题目给出的是一个树,其中\(\frac{i}{K}\)是\(i\)的父亲节点

    attack
  • 洛谷P5245 【模板】多项式快速幂(多项式ln 多项式exp)

    attack
  • 【CodeForces 730H】Car Repair Shop

    模拟,先看从s[i]时刻开始修理,和之前i-1个是否冲突。如果冲突,就枚举每个s[j]+d[j]时刻开始,看是否冲突,再从中选择最小的时刻。

    饶文津
  • 数组的简单练习题

    1.将一个给定的整型数组转置输出, 例如: 源数组,1 2 3 4 5 6 转置之后的数组,6 5 4 3 2 1

    阮键
  • 洛谷P3763 [TJOI2017]DNA(后缀数组 RMQ)

    具体来说,每次比较当前后缀和\(S_0\)的lcp,如果长度\(< N\)的话就从不合法的位置继续匹配

    attack
  • Lake Counting (POJ No.2386)

    题意:有一个M*N的圈子,雨后有积水,然后八个方位相联通的被认为是连接在一起的。请求出圈子里共有多少个水洼。

    用户7727433
  • HDU 4786Fibonacci Tree(最小生成树)

    Problem Description   Coach Pang is interested in Fibonacci numbers while Un...

    attack
  • C++ 函数指针的定义方法及使用

    第一种,c语言通用。定义一个process_job函数指针类型,返回值为 int ,函数参数为int a,int b。使用用两种方法。

    forxtz
  • 口算训练 HDU - 6287

    小Q非常喜欢数学,但是他的口算能力非常弱。因此他找到了小T,给了小T一个长度为n的正整数序列a1,a2,…,an,要求小T抛出m个问题以训练他的口算能力。

    用户7727433

扫码关注云+社区

领取腾讯云代金券