题目亲戚 (洛谷 P1551)题目背景若某个家族人员过于庞大要判断两个人是否是亲戚确实不容易。规定$x$ 和 $y$ 是亲戚$y$ 和 $z$ 是亲戚那么 $x$ 和 $z$ 也是亲戚。也就是亲戚关系具有传递性。题目描述给你 $n$ 个人编号从 1 到 $n$$m$ 对亲戚关系以及 $p$ 个亲戚关系询问。输入格式第一行三个整数 $n, m, p$。$n,m,p \le 5000$接下来 $m$ 行每行两个整数 $M_i, M_j$表示 $M_i$ 和 $M_j$ 具有亲戚关系。接下来 $p$ 行每行两个整数 $P_i, P_j$询问 $P_i$ 和 $P_j$ 是否具有亲戚关系。输出格式一共输出 $p$ 行每行一个Yes或No。表示对于每一个询问的答案。输入输出样例输入样例#1:6 5 3 1 2 1 5 3 4 5 2 1 3 1 4 2 3 5 6输出样例#1:Yes Yes No#includebits/stdc.h using namespace std; #define N 5005 // int fa[N] {0}; int find(int x){ if(fa[x] x){ return x; } else{ fa[x] find(fa[x]); return fa[x]; } } void join(int x, int y){ int fax find(x); int fay find(y); if(fax ! fay){ // fa[fax] fay; } } int main(){ int n, m, p; while(cin n m p){ for(int i 1; i n; i ){ fa[i] i; } int x, y; // 读入关系 for(int i 0; i m; i ){ cin x y; join(x, y); } // 查户口 for(int i 0; i p; i ){ cin x y; if(find(x) find(y)){ cout Yes endl; } else{ cout No endl; } } } return 0; }并查集查看题解 查看答案题目描述Time Limit: 1000 msMemory Limit: 256 mb如题现在有一个并查集你需要完成合并和查询操作。输入输出格式输入描述:第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。 接下来 M 行每行包含三个整数 Zi,Xi,Yi。 当 Zi1 时将 Xi 与 Yi 所在的集合合并。 当 Zi2 时输出 Xi 与 Yi 是否在同一集合内是的输出 Y 否则输出 N 。 1 N 10^4 1 M 2*10^5输出描述:对于每一个 Zi 2 的操作都有一行输出每行包含一个大写字母为 Y 或者 N 。输入输出样例输入样例#:复制4 7 2 1 2 1 1 2 2 1 2 1 3 4 2 1 4 1 2 3 2 1 4输出样例#:复制N Y N Y#includebits/stdc.h using namespace std; #define N 20005 int fa[N] {0}; int find(int x){ if(fa[x] x){ return x; } else{ fa[x] find(fa[x]); return find(fa[x]); } // while(fa[x] ! x){ // x fa[x]; // } // return x; } void join(int x, int y){ int fax find(x); int fay find(y); if(fax fay){ return; } else{ fa[fax] fay; return; } } int main(){ int n, m, p; while(cinnm){ int x, y, z; for(int i 1; i n; i ){ fa[i] i;l } for(int i 0; i m; i ){ cinzxy; if(z 1){ join(x, y); } else{ if(find(x) find(y)){ coutYendl; } else{ coutNendl; } } } } }
并查集（图论）
题目亲戚 (洛谷 P1551)题目背景若某个家族人员过于庞大要判断两个人是否是亲戚确实不容易。规定$x$ 和 $y$ 是亲戚$y$ 和 $z$ 是亲戚那么 $x$ 和 $z$ 也是亲戚。也就是亲戚关系具有传递性。题目描述给你 $n$ 个人编号从 1 到 $n$$m$ 对亲戚关系以及 $p$ 个亲戚关系询问。输入格式第一行三个整数 $n, m, p$。$n,m,p \le 5000$接下来 $m$ 行每行两个整数 $M_i, M_j$表示 $M_i$ 和 $M_j$ 具有亲戚关系。接下来 $p$ 行每行两个整数 $P_i, P_j$询问 $P_i$ 和 $P_j$ 是否具有亲戚关系。输出格式一共输出 $p$ 行每行一个Yes或No。表示对于每一个询问的答案。输入输出样例输入样例#1:6 5 3 1 2 1 5 3 4 5 2 1 3 1 4 2 3 5 6输出样例#1:Yes Yes No#includebits/stdc.h using namespace std; #define N 5005 // int fa[N] {0}; int find(int x){ if(fa[x] x){ return x; } else{ fa[x] find(fa[x]); return fa[x]; } } void join(int x, int y){ int fax find(x); int fay find(y); if(fax ! fay){ // fa[fax] fay; } } int main(){ int n, m, p; while(cin n m p){ for(int i 1; i n; i ){ fa[i] i; } int x, y; // 读入关系 for(int i 0; i m; i ){ cin x y; join(x, y); } // 查户口 for(int i 0; i p; i ){ cin x y; if(find(x) find(y)){ cout Yes endl; } else{ cout No endl; } } } return 0; }并查集查看题解 查看答案题目描述Time Limit: 1000 msMemory Limit: 256 mb如题现在有一个并查集你需要完成合并和查询操作。输入输出格式输入描述:第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。 接下来 M 行每行包含三个整数 Zi,Xi,Yi。 当 Zi1 时将 Xi 与 Yi 所在的集合合并。 当 Zi2 时输出 Xi 与 Yi 是否在同一集合内是的输出 Y 否则输出 N 。 1 N 10^4 1 M 2*10^5输出描述:对于每一个 Zi 2 的操作都有一行输出每行包含一个大写字母为 Y 或者 N 。输入输出样例输入样例#:复制4 7 2 1 2 1 1 2 2 1 2 1 3 4 2 1 4 1 2 3 2 1 4输出样例#:复制N Y N Y#includebits/stdc.h using namespace std; #define N 20005 int fa[N] {0}; int find(int x){ if(fa[x] x){ return x; } else{ fa[x] find(fa[x]); return find(fa[x]); } // while(fa[x] ! x){ // x fa[x]; // } // return x; } void join(int x, int y){ int fax find(x); int fay find(y); if(fax fay){ return; } else{ fa[fax] fay; return; } } int main(){ int n, m, p; while(cinnm){ int x, y, z; for(int i 1; i n; i ){ fa[i] i;l } for(int i 0; i m; i ){ cinzxy; if(z 1){ join(x, y); } else{ if(find(x) find(y)){ coutYendl; } else{ coutNendl; } } } } }
