내용을 기반으로하는 하위 목록 병합, python 3

Question

정수가 포함 된 하위 목록 (쌍)을 포함하는 여러 목록이있는 경우. 두 개의 하위 목록에 동일한 번호가있는 경우이를 병합하고 중복 된 자릿수를 지우려고합니다. 예를 들어

: alist = [[2, 1], [5, 3], [5, 1], [3, 4], [3, 1], [5, 4], [4, 1], [5, 2], [4, 2]] becomes alist = [1,2,3,4,5] 그리고 결과들이 공통으로 모든 공유 숫자 될 일이 있기 때문에 하나 개의 목록에 병합 그들 모두 일 것이다. alist = [[4,5],[7,8],[6,7],[9,5]] 이 될 것입니다 : alist = [[4,5,9],[6,7,8]] 문제는 내가 그들을 10^7 항목으로, 거대한 목록을 반복하고있어입니다

하지만 모든 목록이 너무 편리하지 않습니다

. 두 개의 중첩 루프없이이 작업을 완료하는 방법이 있습니까? 그게 내가 현재하고있는 일이다.

Answer 1

먼저 쌍이 쌍으로 구성된 번호로 색인화 된 해시 테이블을 생성하여 어떤 쌍이 구성원을 공유하는지 확인할 수 있습니다.

이제 노드가 쌍으로되어 있고 두 쌍이 연결된 그래프에서 연결된 구성 요소 (https://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29)를 찾는 것으로 문제를 볼 수 있습니다. 위키 피 디아 엔트리 노트에서 깊이 우선 검색을 사용하여 그래프의 모든 노드를 방문하고 깊이 우선 검색을 사용하여 노드의 모든 직접 연결과 간접 연결을 따라 같은 구성 요소. 또 다른 접근법은 https://en.wikipedia.org/wiki/Disjoint-set_data_structure을 사용하여 이전에 다른 세트의 두 쌍이 번호를 공유 할 때 세트를 병합하여 세트 세트를 유지하는 것입니다.