모서리 집합에서 자식 - 부모 관계를 얻는 방법

Question

트리 구조를 갖도록 주어진 그래프로 작업하고 있습니다. 그래프의 모서리 집합을 부모 - 자식 관계에 매핑하려고합니다. 나는 관계를 저장하기 위해 파이썬 사전을 사용하고있다. 예를 들어 설명해 보겠습니다. 내가 주어진 5 개 노드와 가장자리와 그래프가 있다고 가정은 다음과 같습니다

가

2 1 
3 1 
4 2 
5 2 

코드 :

paths = {} 
n = int(raw_input())  ##number of nodes 
j = 1 
while j < n: 
    u, v = raw_input().split(" ") 
    paths[int(v)] = int(u) 
    j += 1 

그래서 내 사전 {2:1, 3:1, 4:2, 5:2} 될 것이다.

그러나 가장자리가 역순으로 제공하는 경우 코드는 실패합니다 :이 경우

1 2 
1 3 
2 4 
2 5 

내 사전 {1:3, 2:5} 될 것이라고 나는 두 가장자리를 놓쳤다.

어떻게 코드를보다 견고하게 만들 수 있습니까?

편집 : 각 가장자리를 들면, 나는 아이 인 노드 말할 수 있어야하고 사전 다음과 같은 방법을 사용하면 어떤 노드는 부모

Answer 1

입니다 :.

paths[int(v)] = int(u) 

키를 가리키는 값을 목록에 추가하는 대신 재 지정하십시오.

내가 제대로 이해하면 다음을 사용한다 :

paths = [] 
n = int(raw_input())  ##number of nodes 
j = 1 
while j < n: 
    u, v = raw_input().split(" ") 
    paths.append(int(u), int(v)) 
    j += 1 

그것은 최소한의 입력 순서에 의존하지 않습니다.