1 条题解
-
0Shuchong (绿蓝之上の书虫) LV 9 MOD @ 2020-05-09 14:16:09
并查集,很简单
- 操作 \(1\):查找两点连通性,
find
函数,使用f
数组记录 - 操作 \(2\):连通两点,在
find
不连通下,使用f
数组和unionSet
函数合并
#include <bits/stdc++.h> using namespace std; int f[20086]; void makeSet (int size) { for (int i = 1; i <= size; i++) f[i] = i; return; } int find (int x) { if (x != f[x]) f[x] = find(f[x]); return f[x]; } void unionSet (int x, int y) { x = find(x); y = find(y); if (x == y) return; f[x] = y; } int main () { int n, m; scanf("%d%d", &n, &m); makeSet(n); for (int i = 1; i <= m; i++) { int z, x, y; scanf("%d%d%d", &z, &x, &y); if (z == 1) unionSet(x, y); else if (find(x) == find(y)) printf("Y\n"); else printf("N\n"); } return 0; }
- 操作 \(1\):查找两点连通性,
- 1