给定若干个32位int数字集合,每个集合中的数字无重复,譬如:
{1,2,3} {2,5,6} {8}
将其中交集不为空的集合合并,保证合并完成后所有集合之间无交集,输出合并后的集合个数以及最大集合中元素的个数。
输入格式:
1. 第一行为一个数字N,表示集合数。
2. 接下来N行,每行一个非空集合,包含若干个数字,数字之间用空格分开。
假设第i个集合的大小为Si,数据满足N<=100000,ΣSi<=500000
输出格式:
1. 第一行为合并后的集合个数。
2. 第二个为最大集合中元素的个数。
3 1 2 3 2 5 6 8
2 5
while True: try: n = int(input()) a = [] maxlth = 0 for i in range(n): data = {int(x) for x in input().split()} a.append(data) maxlth = max(maxlth, len(data)) j = len(a) b = [] while j > 1: if len(a[-1] & a[j-2]) > 0: b.append(j-2) j -= 1 for k in b: a[-1] |= a[k] maxlth = max(maxlth, len(a[-1])) a.pop(k) print(len(a)) print(maxlth) except: break讨论区也有并查集算法,大家可以学习一下,我也在学习