Union & Find Algorithm

[Jinsujin]

• ex) 팀원이 몇명인가, 서로 친구인가 판별
• 크루스칼 알고리즘에 사용: 사이클이 없는 트리를 만들기 위해 Union&Find 활용

base code

    // 1. 그래프 초기화
    var graph = Array(repeating: 0, count: n+1)
    for i in 1...9 {
        graph[i] = i
    }

    // 2. node 가 속한 집합 노드번호를 반환
    func find(_ node: Int) -> Int {
        if graph[node] == node { return node }
        
        // 일렬로 노드를 연결하므로 탐색횟수가 크다
        // [0, 2, 3, 4, 5, 5, 7, 8, 9, 9]
//        return find(graph[node])
        
        // 반환값을 배열에 저장해 경로를 압축=> 시간복잡도 감소
        // [0, 4, 4, 5, 5, 5, 7, 8, 9, 9]
        graph[node] = find(graph[node])
        return graph[node]
    }
    
    // 3. a, b 노드를 한 집합으로 만든다
    func union(a: Int, b: Int) {
        // 1. 두 노드가 하나의 집합인지 판별한다
        let fa = find(a)
        let fb = find(b)
        if fa != fb { graph[fa] = fb }
    }