Union Find

정의

서로소 집합(disjoint-set) 자료 구조, 또는 합집합-찾기(union–find) 자료 구조는 다음 연산을 제공한다:

• Find: 어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환한다. 어떤 원소와 각 대표 원소들 간의 find 결과를 비교하여 같은 집합임을 판단한다.
• Union: 두 개의 집합을 하나의 집합으로 합친다.

시간복잡도

Find, Union 모두 O(N)이다. (in worst case)

문제 - 547. Number of Provinces

집합의 개수를 구하는 문제이다.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.
Return the total number of provinces.

Union Find 구현

1. parents 배열을 선언하여 처음엔 자기 자신을 parents로 초기화한다.
2. 노드 간 관계가 연결되면 한 노드의 부모를 다른 노드의 부모로 바꿔준다.
   예를 들어, A-B가 연결되었다면 A와 B의 부모를 구해서 서로 부모가 다르면 B의 부모를 A의 부모로 넣어준다. 주의할 점은 자신의 부모의 부모를 변경하는 것이지, 자신의 부모를 바꾸는게 아니다. 이 말은 소스코드를 보면 더 이해가 잘 간다.
3. 전체 노드 갯수 - 부모가 다른 노드 갯수는 집합의 갯수가 나온다.

class Solution {
public:
    int parents[201];
    int findCircleNum(vector<vector<int>>& isConnected) {
        for (int i = 0; i < isConnected.size(); i++) {
            parents[i] = i;
        }
        
        int cnt = isConnected.size();
        
        for (int i = 0; i < isConnected.size(); i++) {
            for (int j = 0; j < isConnected[i].size(); j++) {
                if (i == j) {
                    continue;
                }
                if (isConnected[i][j] == 1) {
                    int rootA = find(i);
                    int rootB = find(j);
                    
                    if (rootA != rootB) {
                        cnt--;
                        parents[rootB] = rootA;
                    }
                }
            }
        }
        return cnt;
    }
    
    int find(int node) {
        if (node == parents[node])
            return node;
        return find(parents[node]);
    }
};

핵심은 parents[rootB] = rootA; 이 부분이다.
나는 처음에 parents[j] = rootA; 라고 넣으려고 했었다.
자기자신의 부모를 바꾸는게 아니라, 자기 자신의 부모의 부모를 바꾸는 것이다.

find() 함수 구현

재귀로 부모를 찾아간다. 더이상 찾을 부모가 없다면(나의 부모는 나 자신일 경우) 리턴한다.

문제 - 1101. The Earliest Moment When Everyone Become Friends

모든 사람이 친구가 되는 가장 짧은 시간을 구하면 되는 문제이다.

Return the earliest time for which every person became acquainted with every other person.

class Solution {
public:
    int parents[10001];
    int earliestAcq(vector<vector<int>>& logs, int n) {
        sort(logs.begin(), logs.end());
        
        for (int i = 0; i < n; i++) {
            parents[i] = i;
        }
        
        for (int i = 0; i < logs.size(); i++) {
            int rootA = find(logs[i][1]);
            int rootB = find(logs[i][2]);
            if (rootA != rootB) {
                n--;
                if (n == 1) {
                    return logs[i][0];
                }
                parents[rootB] = rootA;
            }
        }
        return -1;
    }
    
    int find(int a) {
        if (a == parents[a]) {
            return a;
        }
        
        return find(parents[a]);
    }
    
};

항상 짧은 시간부터 입력된다는 조건이 없기때문에 logs를 처음에 정렬(sort)했다.