题解 P3367 【【模板】并查集】
interestingLSY
2016-11-13 14:36:17
#题解来啦！
赤裸裸的并查集
data[i]表示i在data[i]集合中
rank数组用来优化（不加也不会TLE=。=）。
##模板送你们，拿去吧！
```cpp
#include <algorithm>
#include <iostream>
#include <string.h>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#define ll long long
#define ull unsigned ll
#define uint unsigned int
#define ld long double
#define uld unsigned ld
#define INF 999999
#define LINF 99999999
#define MOD 1e9 + 7
#define LSY HandSome
using namespace std;
uint n,m;
uint data[100000];
uint rank[100000];
void init(){
for(uint k = 1;k <= n;k++)
data[k] = k, rank[k] = 1;
}
uint find(uint d){
if(data[d] == d) return d;
return find(data[d]);
}
void unite(uint d1,uint d2){
d1 = find(d1); d2 = find(d2);
if(d1 == d2)return;
if(rank[d1] < rank[d2]) data[d1] = d2;
else{
data[d2] = d1;
if(rank[d1] == rank[d2]) rank[d1]++;
}
}
int main(){
//ios_base::sync_with_stdio(false);
//cin.tie(0);
cin >> n >> m;
init();
while(m--){
uint op,d1,d2;
cin >> op >> d1 >> d2;
if(op == 1) unite(d1,d2);
else
if(find(d1) == find(d2)) cout << "Y\n"; else cout << "N\n";
}
return 0;
}
```cpp