我是星星 @ 2017-08-28 21:38:57
#include<iostream>
using namespace std;
int x,y,z,father[10001],n,m;
int find(int t) //找祖宗
{
if(father[t]!=t) return find(father[t]); //如果其父亲不是祖宗，就找父亲的父亲，依次递归
else return t; //如果找到了祖宗，就返回祖宗的值
}
void unionn(int r1,int r2)
{
father[r2]=r1; //r2的父亲是r2，即集合r1.r2下的所有元素有一个共有祖宗，r1
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) father[i]=i;
for(int i=1;i<=m;i++)
{
int r1,r2;
cin>>z>>x>>y;
if(z==1)
{
r1=find(x); //r1表示x的祖宗
r2=find(y); //r2表示y的祖宗
if(r1!=r2) unionn(r1,r2);
} //如果r1不等于r2，就将他们两个集合联立为一个集合
else
if(find(x)==find(y)) cout<<"Y"; //find【x】表示x的祖宗
else cout<<"N";
}
return 0;
}by 过期薯条 @ 2017-09-03 10:47:24
@2556937429lq 这是我写的并查集
#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
上面的乱了我重发一遍
#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:53:36
@Errorman碩 感谢你。
虽然我还看不大懂你的代码，但是我尽力。。。。。。。
by 过期薯条 @ 2017-09-03 10:53:39
我。。。。。。
https://paste.ubuntu.com/25455397/
打开链接看吧。。。
by 过期薯条 @ 2017-09-03 10:54:20
@2556937429lq qwq看底下的把。。清晰一些
by 我是星星 @ 2017-09-03 11:18:55
嗯嗯
by 我是星星 @ 2017-09-03 11:19:27
你自己写的啊 ？
by 过期薯条 @ 2017-09-04 17:06:22
@2556937429lq 是的。我一直这样写
by Gypsophila @ 2017-10-03 17:58:12
'''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;
}''' 试试这样路径压缩