@[2556937429lq](/space/show?uid=42808) 这是我写的并查集
```c++
#include <cstdio>
#include <cctype>
const int MAXN = 10010, L = 10000;
int fa[MAXN], rank[MAXN];
inline int getInt() { //读入优化在这个题上效果不明显我只是写着玩玩
char \_c; int sum(0);
while (!isdigit(\_c = getchar()));
do sum = sum \* 10 + \_c - '0';
while (isdigit(\_c = getchar()));
return sum;
}
int getfa(int x) { return fa[x] == x ? x : fa[x] = getfa(fa[x]); }//带有路径压缩的find
inline bool \_query(int x, int y) { return getfa(x) == getfa(y) ? true : false; } //查询
inline void \_union(int x, int y) { //启发式合并
int fx = getfa(x), fy = getfa(y);
if (rank[fx] >= rank[fy]) fa[fy] = fx, ++rank[fx];
else fa[fx] = fy, ++rank[fy];
}
int main() {
int n = getInt(), m = getInt();
for (register int i = 1; i <= n; fa[i] = i, ++i);
for (register int i = 1; i <= m; ++i) {
int cmd = getInt(), x = getInt(), y = getInt();
if (cmd - 1) printf(\_query(x, y) ? "Y\n" : "N\n");
else \_union(x, y);
} return 0;
}
by 过期薯条 @ 2017-09-03 10:47:24
上面的乱了我重发一遍
```c++
#include <cstdio>
#include <cctype>
const int MAXN = 10010, L = 10000;
int fa[MAXN], rank[MAXN];
inline int getInt() { //读入优化，无视即可
char _c; int sum(0);
while (!isdigit(_c = getchar()));
do sum = sum * 10 + _c - '0';
while (isdigit(_c = getchar()));
return sum;
}
int getfa(int x) { return fa[x] == x ? x : fa[x] = getfa(fa[x]); } //带路径压缩的find
inline bool _query(int x, int y) { return getfa(x) == getfa(y) ? true : false; } //查询
inline void _union(int x, int y) { //启发式合并
int fx = getfa(x), fy = getfa(y);
if (rank[fx] >= rank[fy]) fa[fy] = fx, ++rank[fx];
else fa[fx] = fy, ++rank[fy];
}
int main() {
int n = getInt(), m = getInt();
for (register int i = 1; i <= n; fa[i] = i, ++i);
for (register int i = 1; i <= m; ++i) {
int cmd = getInt(), x = getInt(), y = getInt();
if (cmd - 1) printf(_query(x, y) ? "Y\n" : "N\n");
else _union(x, y);
} return 0;
}
```
by 过期薯条 @ 2017-09-03 10:50:40
@[Errorman碩](/space/show?uid=18936) 感谢你。
虽然我还看不大懂你的代码，但是我尽力。。。。。。。
by 我是星星 @ 2017-09-03 10:53:36
我。。。。。。
https://paste.ubuntu.com/25455397/
打开链接看吧。。。
by 过期薯条 @ 2017-09-03 10:53:39
@[2556937429lq](/space/show?uid=42808) qwq看底下的把。。清晰一些
by 过期薯条 @ 2017-09-03 10:54:20
嗯嗯
by 我是星星 @ 2017-09-03 11:18:55
你自己写的啊 ？
by 我是星星 @ 2017-09-03 11:19:27
@[2556937429lq](/space/show?uid=42808) 是的。我一直这样写
by 过期薯条 @ 2017-09-04 17:06:22
'''cpp
```cpp
#include<bits/stdc++.h>
using namespace std;
int n, m, fa[11000];
int fif(int q)
{
if(fa[q] == q) return q;
fa[q] = fif(fa[q]);
return fa[q];
}
void invo(int i, int j)
{
int fathi, fathj;
fathi = fif(i);
fathj = fif(j);
fa[fathi] = fathj;
}
bool find(int i, int j)
{
if(fif(i) == fif(j)) return true;
return false;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1;i <= n;i++) fa[i] = i;
for(int i = 1;i <= m;i++)
{
int d;
int t1, t2;
scanf("%d%d%d", &d, &t1, &t2);
if(d == 1) invo(t1, t2);
if(d == 2)
{
bool m = find(t1, t2);
if(m) printf("Y\n");
else printf("N\n");
}
}
return 0;
}
```
'''
试试这样路径压缩
by Gypsophila @ 2017-10-03 17:58:12