5265 : A66 - 연결 쿼리
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
정점 수 $N$ 의 그래프에 대해 다음 2종류의 쿼리를 빠르게 처리하세요.
처음에는 간선이 하나도 없으며, 쿼리의 수는 $Q$ 개입니다.
[제약 조건]
• $2 \le N \le 100000$
• $1 \le Q \le 100000$
• $\operatorname{Query}_i\ (1\le i\le Q)$ 는 모두 $t_i$ $u_i$ $v_i$ 의 형식
• $t_i \in \{1,2\}\ (1\le i\le Q)$
• $1 \le u_i \lt v_i \le N\ (1\le i\le Q)$
• 입력되는 모든 값은 정수입니다.
- 쿼리 1: 정점 $u$ 와 정점 $v$ 를 양방향으로 연결하는 간선을 추가한다.
- 쿼리 2: 정점 $u$ 와 정점 $v$ 가 같은 연결 성분에 속하는지 답한다.
처음에는 간선이 하나도 없으며, 쿼리의 수는 $Q$ 개입니다.
[제약 조건]
• $2 \le N \le 100000$
• $1 \le Q \le 100000$
• $\operatorname{Query}_i\ (1\le i\le Q)$ 는 모두 $t_i$ $u_i$ $v_i$ 의 형식
• $t_i \in \{1,2\}\ (1\le i\le Q)$
• $1 \le u_i \lt v_i \le N\ (1\le i\le Q)$
• 입력되는 모든 값은 정수입니다.
입력 설명
첫째 줄에 $N, Q$ 가 주어집니다.
둘째 줄부터 $Q$ 개의 줄에 걸쳐 쿼리가 주어집니다.
둘째 줄부터 $Q$ 개의 줄에 걸쳐 쿼리가 주어집니다.
출력 설명
각 쿼리 2에 대해 같은 연결 성분이면 `Yes`, 아니면 `No`를 출력하세요.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 4
1 1 2
2 1 3
1 2 3
2 2 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
No
Yes