Obj_432 @ 2018-09-22 10:15:31
代码如下
#include <iostream>
#include <algorithm>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::ios;
using std::vector;
vector<int> s;
int s_size, count; //记录并查集中集合的个数
int size = s.size();
void make_set() {
//初始化,创建了n个集合
for(int i = 0; i < size; i++)
s[i] = -1; //-1表示根的父节点,s[i]表示秩
}
int find(int elements)
{
if(s[elements] < 0)
return elements;
else
return s[elements] = find(s[elements]);
}
//合并以r1和r2为代表的两个集合
void union_set(int r1, int r2) {
if(find(r1) == find(r2))
return; //已连通
if(s[r2] > s[r1])
s[r1] = r2;
else{
if(s[r1] == s[r2])
s[r1]--;
s[r2] = r1;
}
count--; //合并一次子树数目减1
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int a, b, p1, p2, p3;
cin >> a >> b;
for(int i = 0; i < a; i++)
s.push_back(i);
size = s.size();
make_set();
for(int i = 0; i < b; i++){
cin >> p1 >> p2 >> p3;
if(p1 == 1) union_set(p2, p3);
else
if(find(p2) == find(p3))
cout << "Y" << endl;
else
cout << "N" << endl;
}
return 0;
}
by NaCly_Fish @ 2018-09-22 10:27:55
代码怎么这么长。。写一个
by NaCly_Fish @ 2018-09-22 10:29:08
还有
by Obj_432 @ 2018-09-22 10:34:43
@NaCly_Fish 动态数组
by Obj_432 @ 2018-09-22 10:40:26
好吧我脑抽了,写了一堆没卵用的东西
by Obj_432 @ 2018-09-22 10:45:43
已经过了,谢谢各位dalao