0

我有问题和解决方案。但解决方案似乎并不满足所有测试用例：

问题：

变量 N 表示命名边界(0,N-1) 变量 K 表示测试用例的数量

每个测试用例的格式为 (x,y)...(a,b)

这样如果 (x,y) 给定 x,y 属于同一类，如果 (x,y) 和 (y,z) 给定 x,y,z 属于同一类

输出应该是从不同类别中选择 2 个项目的可能方式的数量

解决方案 ：

inp=raw_input()
inp1=inp.split(' ')

n=int(inp1[0])
k=int(inp1[1])

classes=[[]for i in xrange(0,n)]
no_classes=0

def in_list(c):
    for i in range(0,no_classes):
        if c in classes[i]:
            return i;

    return -1



for i in range(0,k):
    inp=raw_input()
    inp1=inp.split(' ')
    c1=int(inp1[0])
    c2=int(inp1[1])

    l1=in_list(c1)
    l2=in_list(c2)

    if l1<0 and l2<0:
        classes[no_classes].append(c1)
        classes[no_classes].append(c2)
        no_classes+=1
    elif l1>=0 and l2<0:
        classes[l1].append(c2)
    elif l2>=0 and l1<0 :
        classes[l2].append(c1)
    elif l1>=0 and l2>=0 and l1!=l2:
        classes[l1]=list(set(classes[l1]+classes[l2]))
        del classes[l2]
        no_classes-=1        

tot_combntns=0;

for i in range(0,no_classes):
    for j in range(i+1,no_classes):
        tot_combntns=tot_combntns+len(classes[i])*len(classes[j])

print tot_combntns 


Sample test case : 

6 3
0 1
2 3
4 5

ans : 12

5 4
0 1
1 2
2 3
3 4

ans = 0 because there is only one class(0,1,2,3,4)

但我不确定这个解决方案是否满足所有测试用例

4

1 回答 1

1

因为这是一个练习编程挑战，所以我不会给你答案。如果你有能力，我会告诉你足够的东西来弄清楚。我将它留在我认为合理的难度级别。如果您能够创建对象、执行递归等，那么它应该很简单。如果你不能做到这一点，那么未能通过这个编程挑战就表明你需要学习更多基础知识。

如果你有一组n物品，从它们中挑选一对的方法是n*(n-1)/2。从不同类别中挑选一对的方式的数量是挑选一对的方式的数量减去，对于每个类别，从该类别中挑选一对的方式的数量。因此，挑战在于找到类并计算每个类。

弄清楚两个元素属于同一类可能涉及许多可能的推理链。例如，规则(a, b), (x,y), (b, y)暗示a和x属于同一类。你如何有效地遍历所有可能的推理链？一种简单有效的方法是创建一个对象，该对象可以获取任何元素并将其映射到其类中已知的最小成员。（在引擎盖下，它足以将每个不是最小的元素映射到一个较小的已知元素，并根据需要懒惰地找出最小的已知元素。）

弄清楚如何实现该对象，我将其留作练习。照原样，一旦你拥有它，弄清楚如何计算每个班级有多少人。

于 2013-08-04T05:12:41.363 回答