판단 도 연결

판단 그림 의 연관 성 판단 방법 이 비교적 많다. 가장 흔히 볼 수 있 는 것 은 바로 집합, DFS, BFS 등 몇 가지 이다. 인터넷 의 코드 도 매우 많 고 글 은 마지막 에 참고 도 했다. 여기 서 주로 설명 하고 집 을 찾 는 것 이다.
그림 에 오로라 경로 가 존재 하 는 지 판단 하 는 수요 가 있 기 때문에 그림 에 있 는 기본 그림 이 연결 되 는 지 판단 해 야 하기 때문에 알고리즘 을 찾 았 습 니 다. 이 글 은 개인의 이해 와 생각 에 치 우 치고 깊이 이해 하면 참고 할 수 있 습 니 다.
그리고 집합 은 노드 를 기록 하 는 루트 노드 의 배열 (또는 용기, 사전 과 유사) 과 두 함수 (find, join) 로 구성 된다.용기 (배열) 는 각 점 의 뿌리 노드 가 무엇 인지 기록 하고 함수 find 는 특정한 노드 의 뿌리 노드 를 찾 는 데 사 용 됩 니 다. join 함 수 는 두 개의 연결 관 계 를 가 진 노드 를 합 친 것 입 니 다.
코드 먼저 보기:

pre = {}


def find(x):
    r = x
    while pre[r] != r:
        r = pre[r]
    i = x
    while i != r:  #     ，        
        j = pre[i]
        pre[i] = j
        i = j
    return r


def join(x, y):
    fx = find(x)
    fy = find(y)
    if fx != fy:
        # root = min(fx, fy)  #          
        # pre[fx] = root
        # pre[fy] = root
        pre[fx] = fy


def judge(n, edges):
    '''
          
    :param n:    
    :param edges:     
    :return:     
    >>> judge(4, [(0, 1), (2, 0),(2, 3)])
    True
    >>> judge(4, [(2, 0),(2, 3)])
    False
    '''
    for i in range(n):
        pre[i] = i
    for i in range(len(edges)):
        join(edges[i][0], edges[i][1])
    group = 0
    for i in range(n):
        if pre[i] == i:
            group += 1
    if group == 1:
        return True
    else:
        return False


if __name__ == '__main__':
    import doctest
    doctest.testmod()

사고방식 은 다음 과 같다. 그림 의 모든 노드 에 대해 그 뿌리 노드 를 그 자체 로 설정한다.그림 속 의 모든 변 의 두 점 을 합 쳐 조작 한 결과 서로 연 결 된 노드 의 뿌리 노드 가 같은 노드 를 가리 키 는 것 을 얻 었 다.따라서 결과 에서 노드 의 뿌리 노드 가 그 자체 의 노드 의 수량 과 같 으 면 이 그림 이 연 결 된 몇 부분 으로 나 뉘 어 져 있 는 지 알 수 있 고 연결 되면 1 이다.
pre 사전 에는 각 노드 의 루트 노드 가 저장 되 어 있 습 니 다. find 가 시작 되 기 전에 초기 화 해 야 합 니 다.find 함 수 는 층 층 이 찾 은 끝 에 x 의 뿌리 노드 를 찾 아 되 돌 아 옵 니 다.join 함 수 는 변 의 두 점 에 속 하 는 집합 을 합병 합 니 다. 만약 에 두 노드 의 뿌리 노드 가 다 르 면 그 중의 한 노드 를 다른 노드 의 부모 노드 로 지정 하여 소속 집합 을 합병 하 는 효 과 를 얻 을 수 있 습 니 다.
최종 적 으로 pre 에서 자체 가 부모 노드 의 정점 수 를 판단 하면 연결 성 을 판단 할 수 있다.경로 압축 과 부모 노드 선택 은 전체 관계 트 리 의 차원 을 균형 시 키 는 방법 으로 스스로 체험 한다.
참고: EOJ 1816 판단 그림 연결 의 세 가지 방법 - dfs, bfs, 그리고 무 방향 그림 의 연관 성 문제 (및 집합) 를 찾 아 사랑 하 는 것 과 집합 을 찾 습 니 다 ~