0919-test3(并查集一定不要n^2关联）

并查集

路径压缩
count列表记录每个集合中元素的个数

#并查集
#getf函数以及merge函数
#getf函数中可以路径压缩
#merge函数中count数组，可以计算出每个集合的元素个数
#使用了count数组，getFather(0)

while True:
    m,n=map(int,input().split(' '))
    if m==0 and n==0:break
    father=[i for i in range(0,m)]
    count=[1 for i in range(0,m)]
    def getFather(x):
        if x!=father[x]:
            father[x]=getFather(father[x])
        return father[x]
    def merge(x,y):
        father_x=getFather(x)
        father_y=getFather(y)
        if father_x!=father_y:
            father[father_y]=father_x
            count[father_x]+=count[father_y]
    for _ in range(0,n):
        link=list(map(int,input().split(' ')))
        link.pop(0)
        for i in range(0,len(link)):
            for j in range(i+1,len(link)):
                #一定不要搞混淆了：link[i] link[j] and i j
                merge(link[i],link[j])
    print(count[getFather(0)])

其实还可以做进一步的输入优化

因为做n-1次关联就可以了，而我做了n^2次关联，大大浪费了时间。

while True:
    m,n=map(int,input().split(' '))
    if m==0 and n==0:break
    father=[i for i in range(0,m)]
    count=[1 for i in range(0,m)]
    def getFather(x):
        if x!=father[x]:
            father[x]=getFather(father[x])
        return father[x]
    def merge(x,y):
        father_x=getFather(x)
        father_y=getFather(y)
        if father_x!=father_y:
            father[father_y]=father_x
            count[father_x]+=count[father_y]
    for _ in range(0,n):
        stus=list(map(int,input().split(' ')))
        stus.pop(0)
        base=stus.pop(0)
        for stu in stus:
            merge(stu,base)
    print(count[getFather(0)])

优化之后的效率差距