心得经验总结:星球大战starwar(并查集)

简介: 心得经验总结:星球大战starwar(并查集)

1015: 【JSOI2008】星球大战starwar

Time Limit: 3 Sec Memory Limit: 162 MB

Submit: 5253 Solved: 2395

【Submit】【Status】【Discuss】

Description

  很久以前,在一个遥远的星系,一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天,凭着一个偶然的

机遇,一支反抗军摧毁了帝国的超级武器,并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直

接或间接地连接。 但好景不长,很快帝国又重新造出了他的超级武器。凭借这超级武器的力量,帝国开始有计划

地摧毁反抗军占领的星球。由于星球的不断被摧毁,两个星球之间的通讯通道也开始不可靠起来。现在,反抗军首

领交给你一个任务:给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序,以尽量快的速度求出每

一次打击之后反抗军占据的星球的连通快的个数。(如果两个星球可以通过现存的以太通道直接或间接地连通,则

这两个星球在同一个连通块中)。

Input

  输入文件第一行包含两个整数,N (1 < = N < = 2M) 和M (1 < = M < = 200,000),分别表示星球的

数目和以太隧道的数目。星球用 0 ~ N-1的整数编号。接下来的M行,每行包括两个整数X, Y,其中(0 < = X

Y 表示星球x和星球y之间有“以太”隧道,可以直接通讯。接下来的一行为一个整数k,表示将遭受攻击的星球的

数目。接下来的k行,每行有一个整数,按照顺序列出了帝国军的攻击目标。这k个数互不相同,且都在0到n-1的范

围内。

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

//并查集,很容易想到,但是并查集不好删除,所以,就是逆序使用并查集,一步步添加节点,还有就是,求连通块的时候,采用遍历并查集的方法会超时,只能合并就连通块个数-1,加入被破坏的点就+1

1 #include

2 #include

3 #include

4 #include

5 #include

6 #include

7 #include

8 #include [span style="color: rgba(0, 0, 255, 1)">set

9 using namespace std;

10

11 #define MAXN 400005

12

13 int n,m;

14 int T;

15 int f【MAXN】;

16 vector[span style="color: rgba(0, 0, 255, 1)">int

17 int des【MAXN】;

18 bool vis【MAXN】;

19 stack[span style="color: rgba(0, 0, 255, 1)">int

20

21 void Init(int s)

22 {

23 for (int i=0;i

24 {

25 f【i】=i;

26 G【i】.clear();

27 vis【i】=0;

28 }

29 }

30

31 int Find(int x)

32 {

33 if (x!=f【x】)

34 f【x】=Find(f【x】);

35 return f【x】;

36 }

37

38 void He(int a,int b)

39 {

40 int fa = Find(a);

41 int fb = Find(b);

42 if (fa != fb)

43 {

44 f【fa】=f【fb】;

45 T--;

46 }

47 }

48

49 int main()

50 {

51 while (scanf("%d%d",n,m)!=EOF)

52 {

53 Init(n);

54 int a,b;

55 for (int i=0;i

56 {

57 scanf("%d%d",a,b);

58 G【a】.push_back(b);

59 G【b】.push_back(a);

60 }

61

62 int k;//破坏次数

63 cin]k;

64 for (int i=0;i

65 {

66 scanf("%d",des【i】);

67 vis【des【i】】=1;

68 }

69 T=n-k; //初始化

70 for (int i=0;i

71 {

72 if (vis【i】) continue;

73 for (int j=0;j

74 {

75 if (vis【G【i】【j】】) continue;

76 He(i,G【i】【j】);

77 }

78 }

79 ans.push(T);

80 for (int i=k-1;i>=0;i--)

81 {

82 int x = des【i】;

83 vis【x】=0;//可以连通了

84 T++; //新加入点

85 for (int j=0;j

86 {

87 int y = G【x】【j】;

88 if (vis【y】) continue;

89 He(x,y);

90 }//代码效果参考:http://www.ezhiqi.com/bx/art_6439.html

91 ans.push(T);

92 }

93 while (!ans.empty())

94 {

95 printf("%d\n",ans.top());

96 ans.pop();

97 }//代码效果参考:http://www.ezhiqi.com/zx/art_5218.html

98 }

99 return 0;

100 }//代码效果参考:http://www.ezhiqi.com/zx/art_1516.html

View Code

目录
打赏
0
0
0
0
39
分享
相关文章
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构的基本概念;算法的基本概念、特性以及时间复杂度、空间复杂度等举例说明;【含常见的报错问题及其对应的解决方法】
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
8月前
|
【C++航海王:追寻罗杰的编程之路】一篇文章带你了解二叉搜索树
【C++航海王:追寻罗杰的编程之路】一篇文章带你了解二叉搜索树
44 1
|
9月前
|
孤独的树(牛客月赛)
孤独的树(牛客月赛)
48 0
LeetCode 周赛上分之旅 #34 按部就班地解决动态规划问题
学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。
76 0
LeetCode 周赛 345(2023/05/14)体验一题多解的算法之美
大家好,我是小彭。这场周赛是 LeetCode 第 345 场单周赛,整体难度不高,我们使用一题多解的方式强化练习。
142 0

相关实验场景

更多
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等