서로 교차하지 않다

서로 교차하지 않음(DSU)

개술

서로 교차하지 않는 데이터 구조는 두 항목이 같은 집중에 있는지 (또는 같은 효과로 두 정점이 같은 연결 구성 요소에 있는지 확인하는 것) 을 신속하게 확정할 수 있고, 두 개의 집합을 빠르게 통합할 수 있으며 (또는 같은 효과로 두 개의 연결 구성 요소를 하나의 연결 구성 요소로 통합할 수 있다.)

이음매

initSet(N)* 요소를 초기화하고 자체 세트로 설정

연합집(i, j)*에서 두 원소를 취하여 하나의 집합으로 조합

findSet(i)* 원소에 속하는 집합 찾기

isSameSet(i, j) 두 요소가 같은 집합에 속하는지 찾기

numDisjointSets 집합 찾기 (연결된 구성 요소)

sizeOfSet 원소가 속한 집합의 크기 찾기

데이터 구조

가장 간단한 형식에서 DSU는parent라는 정수 그룹으로 그 중에서 각 i항의 부항은parent[i] 또는 그룹에 저장되며 이러한 관계는 하나 이상의 가상 트리를 만든다.

나무에서 6이 7 아래에 있는 것을 볼 수 있다. 왜냐하면 아버지[6]=7이기 때문이다.또한 2와 3에는 부모 대상이 없다. 왜냐하면 부모 대상[2]=2, 부모 대상[3]=3이기 때문이다.
모든 나무는 서로 교차하지 않는 집합이다.두 요소가 같은 나무에 있으면, 같은 교차하지 않는 집중에 있다.모든 나무의 뿌리 노드(또는 맨 위의 노드)를 집합의 대표라고 부른다.각 조는 모두 독특한 대표가 있다.보시다시피 내가 집합의 대표라면 아버지 [i]=i. 만약 내가 그의 집합의 대표가 아니라면 나무를 따라 위로 이동해서 대표를 찾을 때까지 이동할 수 있다.

단순(천진)한 실현

DSU의 간단한 구현을 작성할 수 있습니다.이것은 비효율적인 것이지만, 다음에 우리는 두 가지 기술을 사용하여 그것을 개선하여 작업 시간을 거의 고정시킬 것이다.
dsu의 세 가지 주요 기능은 다음과 같습니다.

initSet(N)은 처음에 모든 요소가 자신의 집합에 속하기 때문에 우리는 이를 자신의 부원소로 설정했다.

findSet(v)간단한 귀속 함수로 원소의 부모 원소가 그 원소가 집합의 뿌리에 도달할 때까지 올라간다.

unionSet(a,b)은 두 개의 집합을 조합하려면 먼저 그것들이 같은 집합에 속하는지 확인해야 한다(이미 연합).만약 그렇지 않다면, 우리는 j의 부항을 i로 설정하여, 그것들을 같은 집합에 분배합니다.

vector < int > parent;

void initSet(int N)
{
    parent.assign(N, 0);
    for (int i = 0; i < N; i++)
        parent[i] = i;
}

int findSet(int i)
{
    if (i == parent[i])
        return i;
    return findSet(parent[i]);
}

void unionSet(int i, int j)
{
    i = findSet(i);
    j = findSet(j);
    if (i != j)
        parent[j] = i;
}

그러나 이러한 실현은 낮은 효과로 여겨진다. 큰 나무를 구축하면 서로 다른 체인의 깊이가 더 커지고findSet 함수의 최악의 상황은 O(n)이기 때문이다.

효율적인 구현

더욱 효율적인 DSU를 구축하기 위해 경로 압축과 순서대로 조합하는 두 가지 최적화가 있다.

경로 압축

일반적으로findSet을 사용하여 원소 집합을 찾을 때, 귀속 함수는 원소의 전체 부모 체인을 이 집합의 대표나 유효한 부모 체인에 도달할 때까지 옮겨다니며, 이러한 조작의 복잡성은 O(n)로 하여금 원소의 직접적인 조상이 아니라 최고의 조상을 저장하는 것을 피하게 한다.

경로 압축 개념을 적용한 새findSet () 은 다음과 같습니다. 찾은 부모 단계로 돌아가지 않고 이 동작을 실행하기 전에 저장해야 합니다.
unionSet ()가findSet () 를 두 번 호출하고 복잡도 계산에서 무시한 다른 O (1) 작업을 실행하면 경로 압축 개념을 적용한 후의 복잡도는 O (logn) 에 불과하기 때문에findSet () 의 O (logn) 에 집중되었음을 증명합니다.

int findSet (int i) {
    if (i == parent[i])
        return i;
    return parent[i] = findSet (parent[i]);
}

등급별 연합

이전의 개선은findSet () 동작을 변경하여 나무의 높이를 작게 했습니다.이러한 개선을'순차적 합집'(Union by Rank)이라고 하는데, 이는 유니온셋(unionSet) 조작을 바꾸어 나무의 높이를 작게 만든다.그 기본 사상은 두 개의 집합을 연결할 때 비교적 짧은 집합이 비교적 긴 집합의 하위 집합이 되면 나무의 높이가 작아진다는 것이다.
이런 기술은 두 가지 변체가 있는데 하나는 나무의 크기(정수리)를 바탕으로 나무를 정렬하고 다른 하나는 나무의 깊이를 바탕으로 한다.이 예에서 우리는 나무의 깊이와 집합의 질적 변수를 실현할 것이다.
이를 실현하기 위해 각 노드의 질은 처음에 0으로 설정된 다음에 새로운 노드를 추가할 때마다 점차 증가한다.
분류 기술만 사용하는 복잡성은 효과적으로 O(logn)로 감소

vector < int > parent;
vector < int > rank;

void initSet(int N)
{
    rank.assign(N, 0); //Rank is now initialized
    parent.assign(N, 0);
    for (int i = 0; i < N; i++)
        parent[i] = i;
}

void unionSet(int i, int j)
{
    i = findSet(i);
    j = findSet(j);
    if (i != j)
    {
        int x = findSet(i), y = findSet(j);
        if (rank[x] > rank[y])
            parent[y] = x;

        else
        {
            parent[x] = y;
            if (rank[x] == rank[y])
                rank[y]++; //Rank update
        }
    }
}                   

개선된 복잡성

하나의 경로의 집합 뒤에 하나의 경로의 복잡도를 덧붙여서(또는 하나의 경로의 집합 뒤에 하나의 경로의 복잡도를 덧붙여서)
이 두 가지 기술을 결합하면 복잡성이 고정된 시간에 가까워진다(1)

이 모든 것을 함께 놓아라

응용 경로의 압축과 순서에 따라 집합된 완전한 종류.세 가지 조작이 추가되었음을 주의하십시오

isSameSet(i, j) 두 요소가 같은 집합에 속하는지 찾기

numDisjointSets 집합 찾기 (연결된 구성 요소)

sizeOfSet 요소가 속한 집합의 크기 찾기

class UnionFind //OOP Style class
{ 
    private:
    vector <int>p, rank, setSize;
    int numSets;

    public:
    UnionFind(int N)
    {
        setSize.assign(N, 1);
        numSets = N;
        rank.assign(N, 0);
        p.assign(N, 0);
        for (int i = 0; i < N; i++)
            p[i] = i;
    }
    int findSet(int i) { return (p[i] == i) ? i : (p[i] = findSet(p[i])); }
    bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }
    void unionSet(int i, int j)
    {
        if (!isSameSet(i, j))
        {
            numSets--;
            int x = findSet(i), y = findSet(j);
            if (rank[x] > rank[y])
            {
                p[y] = x;
                setSize[x] += setSize[y];
            }
            else
            {
                p[x] = y;
                setSize[y] += setSize[x];
                if (rank[x] == rank[y])
                    rank[y]++;
            }
        }
    }
    int numDisjointSets() { return numSets; }
    int sizeOfSet(int i) { return setSize[findSet(i)]; }
};</int>

DSU의 일부 응용 프로그램

도면에서 연결된 구성 요소 동적으로 찾기

이미지에서 연결된 구성 요소 검색

정점과 집합

의 대표 사이의 거리를 구한다

나무에서 생명주기 평가 찾기