파이썬에서 조합 수 (transitivity) 고려

Question

질문과 해결책이 있습니다. 그러나 보이지 그다지 용액 모든 테스트 케이스를 만족 될 :

질문 :

변수 N이 명명 경계 (0, N-1) 변수 K는 테스트 케이스의 수를 의미를 나타낸다

각 테스트 (x, y)가 x로 주어지면, y는 같은 클래스 에 속하며 if (x, y)와 (y, z)는 x, y, z가 같은 클래스에 속한다.

출력 다른 클래스에서이 개 항목을 선택 가능한 방법의 수 있어야한다

솔루션 :

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) 

하지만이 솔루션을 만족하는 모든 테스트 케이스

Answer 1

을이 연습 프로그래밍 문제이기 때문에 확실하지 않다, I 너에게 답을주지 않을거야. 당신이 유능한 사람이라면 알아낼 수있을만큼 충분히 말할 것입니다. 나는 합리적인 난이도라고 생각하는 것에 맡기고 있습니다. 당신이 객체를 생성하고 재귀를 수행 할 수 있다면, 그것은 간단해야합니다. 당신이 그럴 능력이 없다면,이 프로그래밍상의 도전에 실패하는 것은 당신이 더 많은 기초를 배울 필요가 있다는 신호입니다.

그룹이 n 인 경우 그 중 한 쌍을 선택하는 방법은 n*(n-1)/2입니다. 서로 다른 클래스에서 한 쌍을 선택하는 방법의 수는 한 쌍을 빼는 방법의 수, 각 클래스에 대해 해당 클래스에서 한 쌍을 선택하는 방법의 수입니다. 그러므로 도전 과제는 클래스를 찾고 각각을 세는 것입니다.

두 요소가 같은 클래스에 속해 있다는 것을 알아 내면 여러 가지 가능한 추론 사슬을 포함 할 수 있습니다. 예를 들어, (a, b), (x,y), (b, y) 규칙은 a과 x이 같은 클래스에 있음을 나타냅니다. 가능한 모든 추론 연쇄를 어떻게 효과적으로 통과합니까? 간단하고 효율적인 방법은 요소를 가져 와서 클래스의 알려진 가장 작은 구성원에 매핑 할 수있는 객체를 만드는 것입니다. 후드에서 최소가 아닌 모든 요소를 ​​작은 알려진 요소에 매핑하고 필요에 따라 가장 작은 알려진 요소를 느리게 파악하는 것으로 충분합니다.)

연습용으로 그 개체를 구현하는 방법 이해하기 . 있는 그대로, 일단 당신이 그것을 가지고, 얼마나 많은 각 클래스에 있습니다 계산하는 방법을 알아 냈어.