集合合并问题

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

发表评论

邮箱地址不会被公开。 必填项已用*标注