verify/yosupo/data-structure/unionfind.test.cpp
Depends on
Code
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"
#include "template.hpp"
#include "data-structure/dsu.hpp"
int main (){
cin . tie ( nullptr ) -> sync_with_stdio ( false );
int n , q ;
cin >> n >> q ;
DSU dsu ( n );
while ( q -- ){
int t , u , v ;
cin >> t >> u >> v ;
if ( t == 0 ) dsu . merge ( u , v );
else cout << dsu . same ( u , v ) << " \n " ;
}
}
#line 1 "verify/yosupo/data-structure/unionfind.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"
#line 2 "template.hpp"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std ;
using namespace __gnu_pbds ;
using ll = long long ;
using db = long double ;
using vi = vector < int > ;
using vl = vector < ll > ;
using vd = vector < db > ;
using pii = pair < int , int > ;
using pll = pair < ll , ll > ;
using pdd = pair < db , db > ;
const int INF = INT_MAX / 2 ;
const int MOD = 998244353 ;
const int MOD2 = 1000000007 ;
const ll LINF = LLONG_MAX / 2 ;
const db DINF = numeric_limits < db >:: infinity ();
const db EPS = 1e-9 ;
const db PI = acos ( db ( - 1 ));
template < class T >
using ordered_set = tree < T , null_type , less < T > , rb_tree_tag , tree_order_statistics_node_update > ;
template < class T >
using ordered_multiset = tree < T , null_type , less_equal < T > , rb_tree_tag , tree_order_statistics_node_update > ;
mt19937 rng ( chrono :: steady_clock :: now (). time_since_epoch (). count ());
mt19937_64 rng64 ( chrono :: steady_clock :: now (). time_since_epoch (). count ());
#line 2 "data-structure/dsu.hpp"
/**
* Author: Teetat T.
* Date: 2024-06-28
* Description: Disjoint Set Union.
*/
struct DSU {
vector < int > p , sz ;
DSU (){}
DSU ( int n ){ init ( n );}
void init ( int n ){
p . resize ( n );
iota ( p . begin (), p . end (), 0 );
sz . assign ( n , 1 );
}
int find ( int u ){
return p [ u ] == u ? u : p [ u ] = find ( p [ u ]);
}
bool same ( int u , int v ){
return find ( u ) == find ( v );
}
bool merge ( int u , int v ){
u = find ( u ), v = find ( v );
if ( u == v ) return false ;
sz [ u ] += sz [ v ];
p [ v ] = u ;
return true ;
}
int size ( int u ){
return sz [ find ( u )];
}
};
#line 4 "verify/yosupo/data-structure/unionfind.test.cpp"
int main (){
cin . tie ( nullptr ) -> sync_with_stdio ( false );
int n , q ;
cin >> n >> q ;
DSU dsu ( n );
while ( q -- ){
int t , u , v ;
cin >> t >> u >> v ;
if ( t == 0 ) dsu . merge ( u , v );
else cout << dsu . same ( u , v ) << " \n " ;
}
}
Back to top page