注意该题集合的传递性：如A和B在一个集合，B和C在一个集合，那么A和C也在一个集合。这咋一听好像是在说废话，带入更具体的例子：
A和B有共同的爱好1，因此他们是一个集群。B和C有共同的爱好2，因此他们是一个集群。但是就仅看A和C，他们没有共同的爱好，他们是不能构成一个集合的。若加入传递者B，那么A和C可以说是一个集群了。
方法一：
思考这样一个问题：如何判断两个人是否属于一个集群呢？
若两个人的爱好集合有交集，那么他们一定有相同的爱好，那么他们一定属于一个集群。
但是两个人的爱好集合没有交集，并不能说明他们就不是一个集群，他们还是有可能是一个集群的，通过上面的例子就可以知道，可以通过传递性
- 将每个人的爱好集合存起来，用领接表来存，
vector<set<string>> v，即每个元素v[i]都是一个集合set<string>，可以看成链表v[i]的含义为编号为i的爱好集合
- 对所有人的爱好集合进行$C_{n}^{2}$的组合枚举，每次选出两个爱好集合判断是否有交集，如果有交集，则将这两个人合并成一个集合（集群）。
为什么这样做是对的呢？
首先，若两个人的爱好集合有交集，那么他们一定有相同的爱好，那么他们一定属于一个集群，这很好理解。
但是两个人的爱好集合没有交集，并不能说明他们就不是一个集群，他们还是有可能是一个集群的啊？
解释如下：如果两个人的爱好集合没有交集，但实际上他们还是一个集群，那么他们肯定是通过集合的传递性构成一个集合的。如A和B的爱好集合有交集，B和C的爱好集合有交集，但A和C的爱好集合没有交集，但是通过B这一个传递者，A和C可以构成一个集合。在$C_{n}^{2}$的组合枚举过程中，就算先枚举到A和C他们不会构成一个集合，但是之后枚举完A和B，B和C之后，A和C自然就在一个集合中了，因此这种做法是对的。
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
N = 1010
p = [0] * N
nums = [1] * N
n = int(input())
for i in range(1,n + 1):
p[i] = i
li = [0] * N
for i in range(1,n + 1):
se = set(input().split(':')[1].split())
li[i] = se # li[i]代表编号为i的人的爱好集合
for i in range(1,n + 1):# C_{n}^{2}组合型枚举爱好集合
for j in range(1,i):
if li[i] & li[j]: # 如果编号为i,j的人的爱好集合有交集,则将i,j两人合并到一个集合
pi = find(i);pj = find(j)
if pi != pj:
p[pi] = pj
nums[pj] += nums[pi]
res = []
for i in range(1,n + 1):
if p[i] == i:# 如果i是某个集合的根节点，即i是该集合的代表元素
res.append(nums[i])
print(len(res))
res.sort(reverse = True)
print(*res)
方法二：
开个领接表unordered_map<string,vector<string>> di ，di[i]代表爱好为i的人的集合，易知每个链表中的人都是属于同一集群的，因此遍历所有的链表，将同一个链表的人都加入一个集合中（这一步的时间复杂度是线性的，因为只需合并相邻两人到同一集合，或者将每个人和第一个人合并到同一个集合即可）
为什么这种做法是对的？
首先，在同一个链表的人都是有同一爱好的，那么他们肯定是一个集群的，这很容易想到。
那么不在同一个链表的人没有同一爱好，他们也不一定就不是一个集群啊？
在下面的例子中，5号和7号是没有共同爱好的，但是经过遍历链表合并操作，5号和7号还是会被加入到同一集群（因为可以通过3号这一传递者），所以该方法可行。如果说更一般的情况，仍然可以成立，比如将5换成A，7换成C，3换成B。遍历完A和B，A和B在一个集合中了。遍历完B和C，B和C在一个集合中了。因此，A和C自然就在一个集合中了，因此这种做法是对的。
from collections import defaultdict
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
N = 1010
p = [0] * N
nums = [1] * N
n = int(input())
for i in range(1,n + 1):
p[i] = i
di = defaultdict(list)
for i in range(1,n + 1):
for hobby in input().split(':')[1].split():
di[hobby].append(i)
"""
遍历所有的链表，将同一个链表的人都加入一个集合中
"""
for hobbys in di.values():
for i in range(1,len(hobbys)):
a = hobbys[0];b = hobbys[i] # 将每个人和第一个人合并到同一个集合
pa = find(a);pb = find(b)
if pa != pb:
p[pa] = pb
nums[pb] += nums[pa]
res = []
for i in range(1,n + 1):
if p[i] == i: # 如果i是某个集合的根节点，即i是该集合的代表元素
res.append(nums[i])
print(len(res))
res.sort(reverse = True)
print(*res)
