[C#] 분리 집합

---

분리 집합

---

분리 집합

서로 중복되지 않는 부분 집합들로 나누어진 원소들을 관리하는 자료구조.
집합의 합치기(Union), 같은 집합인지 확인(Find) 연산을 수행
여러 개의 그룹 중 두 원소가 같은 그룹에 속하는지 확인, 두 그룹을 합치는 연산을 수행.

예시 문제

1717 줄세우기
n, m 입력 n+1개의 집합, m개의 연산 수
연산 ( x a b)
x = 0 이면 a, b를 합치기
x = 1 이면 a, b 같은 집합인지 확인

Find, Union
Find(x) - 원소 x가 속한 집합의 대표를 찾음.
Union(x, y) - 원소 x가 속한 집합과 y가 속한 집합을 합침.

분리집합 코드

class Program
{
    static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
    static int[] parent;

    static void Main()
    {
        int[] nm = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        int n = nm[0];
        int m = nm[1];

        parent = new int[n + 1];

        for (int i = 0; i <= n; i++)
        {
            parent[i] = i;
        }

        for (int i = 0; i < m; i++) 
        {
            int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int com = input[0];
            int a = input[1];
            int b = input[2];
            if (com==1)
            {
                if (Find(a)==Find(b))
                {
                    sw.WriteLine("YES");
                }
                else
                {
                    sw.WriteLine("NO");
                }
            }
            else
            {
                Union(a, b);
                sw.WriteLine(string.Join(" ", parent));
            }
        }

        sw.Flush(); sw.Close();
    }

    static int Find(int x)
    {
        if (parent[x] !=x)
        {
            parent[x] = Find(parent[x]);
        }
        return parent[x];
    }

    static void Union(int a, int b) 
    {
        a = Find(a);
        b = Find(b);

        if (a!=b)
        {
            if (a < b)
            {
                parent[b] = a;
            }else
            {
                parent[a] = b;
            }
        }
    }
}

분리집합 실행 예시

n = 6 m = 5 실행 예시

분리집합 실행 예시

n = 6 (1 2 3 4 5 6)  
m = 5 (연산의 개수)  

0 1 2 ->  1 1 3 4 5 6  parent[2] = 1;   
0 2 3 ->  1 1 1 4 5 6  parent[3] = 1;
0 5 6 ->  1 1 1 4 5 5  parent[6] = 5;
0 3 6 ->  1 1 1 4 1 5  parent[parent[6]] = parnet[3]; 
                       parent[5]         = 1;
1 1 3 ->  "YES"


----------------------------------------------------------
1. 0 1 2
1
 \
  2  3  4  5  6

2. 0 2 3
  1
 / \
2   3  4  5  6

3. 0 5 6
  1       5
 / \       \
2   3  4    6

4. 0 3 6
  1       
 / \      
2   3       4  
    |
    5
     \
      6

• (1,2,3,5,6), (4)

---

메모

---