# 유니온 파인드

* 유니온 파인드는 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘이다.&#x20;

### 집합 표현하기&#x20;

#### Question

![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2FJMTn3moUmDLUWWN0arCz%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-08-04%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2012.55.12.png?alt=media\&token=c76e94fa-ce5c-4ad1-9012-44002a859eb8)

#### Code

```java
import java.util.Scanner;

public class N50_P1717_집합_표현하기 {

    public static int[] parent;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        parent = new int[N + 1];

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

        for (int i = 0; i < M; i++) {
            int question = sc.nextInt();
            int a = sc.nextInt();
            int b = sc.nextInt();
            if (question == 0) {
                union(a, b);
            } else {
                if (checkSame(a, b)) {
                    System.out.println("YES");
                } else {
                    System.out.println("NO");
                }
            }
        }
    }


    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            parent[b] = a;
        }
    }

    public static int find(int a) {
        if (a == parent[a])
            return a;
        else
            return parent[a] = find(parent[a]);
    }

    public static boolean checkSame(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) {
            return true;
        }
        return false;
    }
}

```

#### Idea

#### reference



### 여행 계획 짜기&#x20;

#### Question - 1976&#x20;

![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2FaN3PljkBF0VqUm6iOEXc%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-08-04%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2012.50.50.png?alt=media\&token=5374f1fe-4210-45d6-838d-274bcc1e910f)

#### Code

```java
import java.util.Scanner;

public class N51_P1976_여행_계획짜기 {
    static int city;
    static int road;
    public static int[] parent;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        city = sc.nextInt();
        road = sc.nextInt();

        int[][] map = new int[city + 1][city + 1];

        for (int i = 1; i <= city; i++) {
            for (int j = 1; j<= city; j++) {
                map[i][j] = sc.nextInt();
            }
        }

        int[] route = new int[road + 1];
        for (int i = 1; i <= road; i++) {
            route[i] = sc.nextInt();
        }

        parent = new int[city + 1];
        for (int i = 1; i <= city; i++) {
            parent[i] = i;
        }

        for (int i =1; i <= city; i++) {
            for (int j = 1; j <= city; j++) {
                if (map[i][j] == 1) {
                    union(i, j);
                }
            }
        }

        // 여행 계획 도시들이 1개의 대표 도시로 연결되어 있는지 확
        int index = find(route[1]);
        for ( int i =2; i < route.length; i++) {
            if (index != find(route[i])) {
                System.out.println("NO");
                return;
            }
        }

        System.out.println("YES");
    }

    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            parent[b] = a;
        }
    }
    public static int find(int a) {
        if (a == parent[a])
            return a;
        else {
            return parent[a] = find(parent[a]);
        }
    }
}
```

#### Idea

* 그래프 이론
* 자료 구조
* 그래프 탐색
* 분리 집합&#x20;

#### reference



### 거짓말쟁기가 되긴 싫어&#x20;

#### Question - 1043&#x20;

![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2FmOI0XHCKAbmitpUgynnj%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-08-04%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2012.51.42.png?alt=media\&token=8ecc973c-1156-4d97-8eba-804ad5fb7bc1)

#### Code

```java
import java.util.ArrayList;
import java.util.Scanner;

public class N52_P1043_거짓말쟁이가_되긴_싫어 {

    public static int[] parent;
    public static int[] avoidInfo;
    public static ArrayList<Integer>[] partyInfo;
    public static int result;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int peopleTotal = sc.nextInt();
        int partyNum = sc.nextInt();
        int avoidNum = sc.nextInt();
        result = 0;

        avoidInfo = new int[avoidNum];
        for (int i = 0; i < avoidNum; i++) {
            avoidInfo[i] = sc.nextInt();
        }

        partyInfo = new ArrayList[partyNum];
        for (int i = 0; i < partyNum; i++) {
            partyInfo[i] = new ArrayList<Integer>();
            int participate = sc.nextInt();
            for (int j = 0; j < participate; j++) {
                partyInfo[i].add(sc.nextInt());
            }
        }

        parent = new int[peopleTotal + 1];
        for (int i = 0; i <= peopleTotal; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < partyNum; i++) {
            int firstPeople = partyInfo[i].get(0);
            for (int j = 1; j < partyInfo[i].size(); j++) {
                union(firstPeople, partyInfo[i].get(j));
            }
        }

        for (int i = 0; i < partyNum; i++) {
            boolean isPossible = true;
            int cur = partyInfo[i].get(0);
            for (int j = 0; j < avoidInfo.length; j++) {
                if (find(cur) == find(avoidInfo[j])) {
                    isPossible = false;
                    break;
                }
            }
            if (isPossible)
                result++;
        }
        System.out.println(result);
    }

    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            parent[b] = a;
        }
    }

    // sss
    public static int find(int a) {
        if (a == parent[a]) {
            return a;
        } else {
            return parent[a] = find(parent[a]);
        }
    }
}
```

#### Idea

#### reference

