首页 > 技术文章 > 朋友(并查集的删除操作 可看作是插入操作的逆序)

fzuhyj 2017-12-17 02:30 原文

z 被选为他们村的村长, 现在小 z 调查他们村上的关系。 如果村民 a 和村
b 是朋友, 村民 b 和村民 c 是朋友, 那么村民 a 和村民 c 也是朋友。 那么村上
的村民就会形成一个“朋友” 团队, 现在小 z 想知道他们村长有多少个这样的团
队。 同时, 他们村会有人离开村子到城里谋求发展, 那么小 z 也想知道, 当他们
离开后村上的“朋友” 团队。
★数据输入
输入第一行包括两个整数, NMN 表示一共有 N 个人, M 表示一个共有
M 对关系。 村民的编号分别为 0~N-1。 接下来 M 行, 每行两个数 uv, 表示村
u 和村民 v 有关系。 接着输入一行一个整数 Q, 表示 Q 组询问, 接下来一行 Q
个数分别表示离开的 Q 个人的编号。
★数据输出
输出一开始有多少个“朋友” 团队, 以及对于每个村民的离开, 输出剩下的
“朋友” 团队。

输入示例 输出示例
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
51
6 3 5 7
111233


★数据范围
70%数据 N<=500,M<=1000,Q<=500
100%数据 N<=10000,M<=50000,Q<=10000

 

推荐阅读