시간 제한 : 2초
메모리 제한 : 128MB

문제

초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력

첫째 줄에 $n$, $m$이 주어진다.
$m$은 입력으로 주어지는 연산의 개수이다. 다음 $m$개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다.

출력

1로 시작하는 입력에 대해서 a와 b가 같은 집합에 포함되어 있으면 "YES" 또는 "yes"를, 그렇지 않다면 "NO" 또는 "no"를 한 줄에 하나씩 출력한다.

제한

1 ≤ n ≤ 1,000,000
1 ≤ m ≤ 100,000
0 ≤ a, b ≤ n
a, b는 정수

a와 b는 같을 수도 있다.

예제 입력
7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

예제 출력
NO
NO
YES

---

제한시간이 2초, 주어진 n,m 크기로 보았을 때 시간복잡도를 O(n^2)으로 가면 시간초과가 나오기때문에 시간복잡도 O(nlogn)으로 생각하고 문제를 접근했다.

처음으로 접근했던 방식은 인접리스트를 구현하여 주어진 a가 b를 거쳐가는지 확인해보는 방법이였다.

const [[N, M], ...input] = require('fs')
  .readFileSync('./dev/stdin')
  .toString()
  .trim()
  .split("\n")
  .map((el) => el.split(" ").map(Number));

const adjArr = Array.from({ length: N + 1 }, () => new Array());
const answer = [];
for (let i = 0; i < M; i++) {
  const [flag, a, b] = input[i];

  if (flag === 0) {
    adjArr[a].push(b);
    adjArr[b].push(a);
  } else {
  <!--메모리 초과나는 부분 -->
    const visited = new Array(N + 1).fill(0);
    const queue = [a];
    visited[a] = 1;
    let idx = 0;
    let flag1 = 0;
    while (idx < queue.length) {
      const cur = queue[idx++];

      if (cur === b) {
        answer.push("YES");
        flag1 = 1;
        break;
      }

      for (let i = 0; i < adjArr[cur].length; i++) {
        const next = adjArr[cur][i];
        if (!visited[next]) {
          queue.push(next);
          visited[next] = 1;
        }
      }
    }
    if (!flag1) answer.push("NO");
  }
}

console.log(answer.join("\n"));

위 코드실행 결과 메모리 초과가 났고 그 이유는 실행 플래그가 1이 나올 때마다 방문배열을 만들어야 했기 때문이다. 물론 시간초과가 나지는 않았지만 같은 집합에 있던 노드들을 한번 확인했음에도 불구하고 매번 새롭게 두 노드가 연결되어있는지 확인해야 했기에 상당히 비효율적인 방법이였다.

하지만 첫번째 방법에서 이미 한번 검색한 노드는 다음번에 검색할 때 두 노드가 연결되어있는지 바로 확인가능해야 한다. 그래서 사용한 방법은 각각의 노드마다 최상위 부모노드를 메모해놓는것이였다. 이렇게 하면 두 노드가 주어졌을 때 각각의 노드의 최상위 부모노드가 같다면 두 노드는 연결되어 있는 즉, 같은 집합에 속한다는것을 알 수 있다.

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output:process.stdout,
});

const tmp = [];

rl.on('line',function(line){
    tmp.push(line);
}).on('close',function(){
    main(tmp);
    process.exit();
})

function main(param){
    const [[N,M],...input] = param.map(el => el.split(' ').map(Number));
const array = new Array(N + 1).fill(null).map((_, idx) => idx);
const answer = [];

<!--최상위 부모노드를 찾고 반환해야주는 함수-->
const find = (x) => {
  if (array[x] === x) return x;
  return (array[x] = find(array[x]));
};

<!--두 노드의 최상위 부모를 찾고 두 노드를 연결시켜주는 함수-->
const _union = (a, b) => {
  const pa = find(a);
  const pb = find(b);

  array[pa] = pb;
};

for (let i = 0; i < M; i++) {
  const [flag, a, b] = input[i];

  if (flag === 0) {
    _union(a, b);
  } else {
    if (find(a) === find(b)) answer.push("YES");
    else answer.push("NO");
  }
}
console.log(answer.join("\n"));

}

배운점

트리를 만들어볼까도 생각했지만 모든 노드들이 주어진 상태가 아니였기에 트리를 만들 수 없었다. 다음부터는 실수하지 말자.