마법 포탈
골드 V의견: 0
마법사의 나라에는 \(N\)개의 지점이 있다. 지점들은 처음에 아무것도 연결되어 있지 않다. 마법사는 두 종류의 명령을 \(Q\)번 내린다.
- 명령 1 \(u\) \(v\): 지점 \(u\)와 지점 \(v\) 사이에 양방향 포탈을 연다. 포탈로 연결된 지점들은 같은 영역에 속하게 된다. (이미 같은 영역이면 아무 변화도 없다.)
- 명령 2 \(u\) \(v\): 지점 \(u\)와 지점 \(v\)가 같은 영역에 속하는지 묻는다.
명령 2가 주어질 때마다 "YES" 또는 "NO"를 출력하여라.
- \(1 \le N \le 100\,000\)
- \(1 \le Q \le 200\,000\)
- \(1 \le u, v \le N\)
- 명령 1과 명령 2가 합쳐서 \(Q\)번 주어진다.
첫째 줄에 지점의 수 \(N\)과 명령의 수 \(Q\)가 공백으로 구분되어 주어진다.
다음 \(Q\)개의 줄에 명령이 주어진다. 각 줄은 1 u v 또는 2 u v 형태이다.
명령 2가 주어질 때마다 한 줄에 "YES" 또는 "NO"를 출력한다.
4 6
1 1 2
1 2 3
2 1 3
2 1 4
1 3 4
2 1 4
YES
NO
YES
처음에 \(1{-}2\), \(2{-}3\) 포탈이 열려 \(\{1,2,3\}\)이 연결된다. \(1\)과 \(3\)은 연결되어 YES, \(1\)과 \(4\)는 연결되지 않아 NO이다. \(3{-}4\) 포탈이 열리면 이제 \(\{1,2,3,4\}\)가 모두 연결되어 마지막 질문도 YES가 된다.
2 3
2 1 2
1 1 2
2 1 2
NO
YES
처음에는 포탈이 없으므로 \(1\)과 \(2\)는 연결되지 않아 NO이다. 포탈을 열면 연결되어 YES가 된다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
마법 포탈
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
마법 포탈