1015: [JSOI2008]星球大战starwar

1015: [JSOI2008]星球大战starwar

Time Limit: 3 Sec  Memory Limit: 162 MB

Submit: 3001  Solved: 1321

[Submit][Status]

Description

很久以前,在一个遥远的星系,一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天,凭着一个偶然的机遇,一支反抗军摧毁了帝国的超级武器,并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。 但好景不长,很快帝国又重新造出了他的超级武器。凭借这超级武器的力量,帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁,两个星球之间的通讯通道也开始不可靠起来。现在,反抗军首领交给你一个任务:给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序,以尽量快的速度求出每一次打击之后反抗军占据的星球的连通快的个数。(如果两个星球可以通过现存的以太通道直接或间接地连通,则这两个星球在同一个连通块中)。

Input

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

Output

输出文件的第一行是开始时星球的连通块个数。接下来的N行,每行一个整数,表示经过该次打击后现存星球的连通块个数。

Sample Input

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

Sample Output

1 1 1 2 3 3

HINT

Source

 题解:正如JSZKC神犇所言——既然并查集不能合并,那么倒着插入不就行了?于是乎我这么做了一下,结果是70分,TLE。。。然后我只好找网上的标程,结果发现了人家在并查集里面有个异常强悍的优化(具体见程序里面的getfat函数),然后就擦着边AC了。。。具体做法是——先把所有边里面没有涉及到被删除点的全部合并,然后按照删点顺序倒着来合并,这一路每次要记录下连通块数量。。。(注意:最后输出时要-i+1,因为假如举个例子,所有的星球在最后的数据中都被干掉了的话,那么假如单纯是连通块的话,应该有N个才是,可是事实上一个星球都没了。。。)

 1 type point=^node;
 2      node=record
 3                 g:longint;
 4                 next:point;
 5      end;
 6 var
 7    i,j,k,l,m,n,t:longint;
 8    a:array[0..400000] of point;
 9    c,b,d,e:array[0..400000] of longint;
10    p:point;
11 function getfat(x:longint):longint;inline;
12          begin
13               if x<>c[x] then
14                  begin
15                       c[x]:=getfat(c[x]);  //orz强悍的优化
16                  end;
17               exit(c[x]);
18          end;
19 function tog(x,y:longint):boolean;inline;
20          begin
21               exit(getfat(x)=getfat(y));
22          end;
23 procedure merge(x,y:longint);inline;
24           begin
25                c[getfat(x)]:=getfat(y);
26           end;
27 procedure add(x,y:longint);inline;
28           var p:point;
29           begin
30                new(p);
31                p^.g:=y;
32                p^.next:=a[x];
33                a[x]:=p;
34           end;
35 begin
36      readln(n,m);
37      for i:=1 to n do
38          begin
39               c[i]:=i;
40               a[i]:=nil;
41          end;
42      for i:=1 to m do
43          begin
44               readln(j,k);
45               add(j+1,k+1);add(k+1,j+1);
46          end;
47      fillchar(b,sizeof(b),0);
48      readln(t);
49      for i:=1 to t do
50          begin
51               readln(d[i]);
52               d[i]:=d[i]+1;
53               b[d[i]]:=1;
54          end;
55      l:=n;
56      for i:=1 to n do
57          begin
58               if b[i]=0 then
59                  begin
60                       p:=a[i];
61                       while p<>nil do
62                             begin
63                                  if b[p^.g]=0 then
64                                     begin
65                                          if not(tog(i,p^.g)) then
66                                             begin
67                                                  dec(l);merge(i,p^.g);
68                                             end;
69                                     end;
70                                  p:=p^.next;
71                             end;
72                  end;
73          end;
74      e[t+1]:=l;
75      for i:=t downto 1 do
76          begin
77               b[d[i]]:=0;
78               p:=a[d[i]];
79               while p<>nil do
80                     begin
81                          if b[p^.g]=0 then
82                             begin
83                                  if not(tog(d[i],p^.g)) then
84                                     begin
85                                          merge(d[i],p^.g);
86                                          dec(l);
87                                     end;
88                             end;
89                          p:=p^.next;
90                     end;
91               e[i]:=l;
92          end;
93      for i:=1 to t+1 do writeln(e[i]-i+1);
94 end.     

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏带你撸出一手好代码

暗号与二进制

「暗号」这个词的意义想必大家都熟悉, 它也是人与人的一种交流方式,只是它的规则并不如我们使用的语言或文字一样由大众所掌握, 因此当人们想传递一些私密的信息又不想...

40714
来自专栏Netkiller

solidity 语言安全·整型溢出

中国广东省深圳市龙华新区民治街道溪山美地 518131 +86 13113668890 <netkiller@msn.com>

48517
来自专栏Python爬虫与算法进阶

一次数据可视化的过程【Excel】

故事是这样的,在知乎上有一个问题叫做: 有哪些质量很高的冷门电影? 有3万多的关注者,181万的浏览量。 ? 今天主要想记录下数据分析的过程。(数据采集并...

3365
来自专栏tkokof 的技术,小趣及杂念

编个“猜数字”玩玩

一日午晌,顿觉百无聊赖,阵阵哈切之余,竟忆起儿时游玩之小游戏,名曰“猜数字”,此物规则甚是简单,游玩之时仅需猜测一四位数字,接着便可得到相应之正误结果,然后依此...

431
来自专栏数据结构与算法

9.22模拟赛解题报告

T2读题就花了半个小时,而且一开始没认真理解题目的意思,前后各dp了一遍,后来仔细揣摩了一下题意,细心品味了一下出题人的语言,正着的dp好像是没用的。。。

813
来自专栏知晓程序

用这款小程序,人人都能写出《霸道总裁爱上我》

1577
来自专栏WOLFRAM

一行代码论英雄—2017 Wolfram 语言“一行代码竞赛”结果

1996
来自专栏编舟记

架构整洁之道导读(一)

我是《架构整洁之道》(Clean Architecture) 中文版的技术审校者,在审校的过程当中略有感悟,所以希望通过撰写导读的方式分享给大家。

3858
来自专栏小文博客

害死人不偿命的(3n+1)猜想 —— 《C语言代码笔记》

1332
来自专栏精讲JAVA

十年之后再看“面向对象”

一起帮里有人问“面向对象”的问题。但我创建“一起帮”的目的是帮人解决“具体的”“实务性的”问题,“面向对象”太过于抽象,所以没批准发布。后来在QQ群里讨论,看他...

1826

扫码关注云+社区