23.10.10

[자료구조] Union-Find (Disjoint Set Union)

1. Disjoint Set

📖 서로소 집합 (Disjoint Set)

두 집합 A,B의 교집합이 공집합일 때, 서로소라고 한다. 두 집합, A, B가 서로소 ⇔ A ∩ B = *ø*
서로 중복된 원소가 없는 집합 (= 교집합이 없는 집합)

2. Union Find

📖 Union-Find
Disjoint Set을 구현한 자료구조

• 지원하는 연산
  • Union 연산: 두 집합을 합치는 연산
  • Find 연산: 원소가 어떤 집합에 속해있는지
• 확인하는 연산 사용하는 경우
  • 특정 원소가 어떤 집합에 속해있는지 확인할 경우
  • 각 집합의 개수를 구할 경우 …

3. 구현

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Node
{
    public Node rootNode;   // 대표 원소
    public int data;       // 원소 값
    public Node nextNode;   // 다음 노드

    public Node(int data)
    {
        this.rootNode = this;
        this.data = data;
        this.nextNode = this;
    }
}

public class DisjointSet
{
    public List<Node> MakeSet(int cnt)
    {
        List<Node> nodes = new List<Node>();
        for(int i = 0; i <= cnt; i++)
        {
            nodes.Add(new Node(i));
        }

		return nodes;
    }

    public Node Find(Node x)
    {
        return x.rootNode;
    }

	public void Union(Node x, Node y)
    {
        Node xRoot = Find(x);
        Node yRoot = Find(y);

        if (xRoot == yRoot) return;
        yRoot.rootNode = xRoot;
        xRoot.nextNode = y;
    }

    public void Disunion(Node y)
    {
        y.rootNode = y;
    }
}