集合合并问题

题目：小明有n只袜子，需要穿m天第i只袜子的颜色为c_i 给出每天要穿的两只袜子的编号（i1,i2) 保证每天穿的袜子颜色一样，最少要对多少只袜子进行染色

思路：根据这m天每天穿的两只袜子，可以将所有袜子分成几个集合，每个集合的颜色都要一样，把集合中所有袜子染成颜色最多的袜子即可将每天穿的袜子标号看作集合，按袜子颜色进行合并，直到每个集合中袜子的标号都不重复实现函数

def maxTint(c,d):
    """
    c: n只袜子的颜色
    d: m天每天穿的袜子的标号
    """
    pass

1，循环标号进行合并

def maxTint(c,d):
    d = map(set,d)
    for ci in range(len(c)):
        new_d = []
        new_g = []
        for di in d:
            if ci in di:
                new_g.append(di)
            else:
                new_d.append(di)
        d = new_d
        if len(new_g)!=0:
            d.append(set())
            for gi in new_g:
                d[-1]=d[-1]|gi
    ans = 0
    for di in d:
        ansi = 0
        for i in di:
            ansi=max(ansi,c.count(c[i-1]))
        ans+=ansi
    return ans

时间复杂度：n*m

#集合合并问题

集合合并问题