学校门户网站建设工作,网上学习做网站,二手房交易网站排名,讯杰网站建设find函数
用于查找一个数字的祖宗数字 比如 初始时#xff0c;每个数字的祖宗是自己 find(i) i 若 要把 3 和 4 合并 则把3的祖宗设置为4 此时 p(find(3)) 4 若 要把 5 和 3 合并#xff0c; 则先找到5和3的祖宗#xff0c; 再把5的祖宗设置为3的祖宗 p[find(5)] find(3)…find函数
用于查找一个数字的祖宗数字 比如 初始时每个数字的祖宗是自己 find(i) i 若 要把 3 和 4 合并 则把3的祖宗设置为4 此时 p(find(3)) 4 若 要把 5 和 3 合并 则先找到5和3的祖宗 再把5的祖宗设置为3的祖宗 p[find(5)] find(3)
int find(int x) {if (p[x] ! x) p[x] find(p[x]);return p[x];
}每次合并集合时只需要更改祖宗元素即可
合并集合
一共有 n个数编号是 1∼n最开始每个数各自在一个集合中。
现在要进行 m个操作操作共有两种
M a b将编号为 a和 b的两个数所在的集合合并如果两个数已经在同个集合中则忽略这个操作 Q a b询问编号为 a和 b的两个数是否在同一个集合中
输入格式 第一行输入整数 n和 m。
接下来 m行每行包含一个操作指令指令为 M a b 或 Q a b 中的一种。
输出格式 对于每个询问指令 Q a b都要输出一个结果如果 a和 b在同一集合内则输出 Yes否则输出 No。
每个结果占一行。
#include iostreamusing namespace std;int p[100100];int find(int a){if(p[a]!a){p[a] find(p[a]);}return p[a];
}int main(){int n,m;cinnm;int i0;for(i1; in;i){p[i] i;}while(m--){string str;int a,b;cinstrab;if(str[0]M){p[find(a)] find(b);}else{if(find(a)find(b)){coutYesendl;}else{coutNoendl;}}}
}连通块中的点的数量
给定一个包含 n个点编号为 1∼n的无向图初始时图中没有边。
现在要进行 m个操作操作共有三种
C a b在点 a和点 b之间连一条边a和 b可能相等 Q1 a b询问点 a和点 b是否在同一个连通块中a和 b可能相等 Q2 a询问点 a所在连通块中点的数量
输入格式 第一行输入整数 n 和 m
接下来 m行每行包含一个操作指令指令为 C a bQ1 a b 或 Q2 a 中的一种。
输出格式 对于每个询问指令 Q1 a b如果 a和 b在同一个连通块中则输出 Yes否则输出 No。
对于每个询问指令 Q2 a输出一个整数表示点 a所在连通块中点的数量
每个结果占一行。
思路 在find的基础上加一个s数组存储以find[i]为祖宗的集合的所有数字的个数
# includeiostreamusing namespace std;int p[100010];
int s[100010];int find(int x){if(p[x]!x) p[x] find(p[x]);return p[x];
}int main(){int n,m;cinnm;int i0;for(i1; in;i){p[i] i;s[i] 1;}while(m--){string str;int a,b;cinstra;if(str[0]C){cinb;if(find(a)find(b)) continue;s[find(b)] s[find(a)];p[find(a)] find(b);}else if(str[1]1){cinb;if(find(a)!find(b)){coutNoendl;}else{coutYesendl;}}else{couts[find(a)]endl;}}}
