Unionfind

AC一覧

Problem Statement
問題文

We have an undirected graph with $N$ vertices and $0$ edges. Process the following $Q$ queries in order:

  • $t_i$ = 0 $u_i$ $v_i$: Add an edge $(u, v)$.
  • $t_i$ = 1 $u_i$ $v_i$: If vertices $u, v$ are connected, print $1$. Otherwise, print $0$.

$N$ 頂点 $0$ 辺の無向グラフに $Q$ 個のクエリが飛んできます。処理してください。

  • $t_i$ = 0 $u_i$ $v_i$: 辺$(u, v)$を追加する。
  • $t_i$ = 1 $u_i$ $v_i$: $u, v$ が連結ならば $1$、そうでないなら $0$ を出力する。

Constraints
制約

Input
入力

$N$ $Q$
$t_1$ $u_1$ $v_1$
$t_2$ $u_2$ $v_2$
:
$t_Q$ $u_Q$ $v_Q$

Sample
サンプル

# 1

4 7
1 0 1
0 0 1
0 2 3
1 0 1
1 1 2
0 0 2
1 1 3
0
1
0
1

Forum


Timelimit: 5 secs

Before submitting, please confirm terms and conditions