Korbin

集合合并问题

题目： 小明有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