并查集基础+优化（下标从0开始）

#include<iostream> #include<algorithm> #include<vector> using namespace std; const int N = 1e5+10; int n,m; int fa[N]; void set(int u,int v) { fa[v] = u; } int find(int arr[],int i) { while(arr[i] != -1) { i = arr[i]; } return i;//返回的是这个节点所在的树的根节点的下标 } int main(void) { cin >> n >> m; for(int i = 0 ; i < n ; i++)//以0为序号 fa[i] = -1; for(int i = 1 ; i <= m ; i++) { int u,v; cin >> u >> v; set(u,v); } for(int i = 0 ; i < n ; i++) cout << fa[i] << " "; int pos1,pos2;//输入像查询节点是否在同一个集合 cin >> pos1 >> pos2; if(find(fa,pos1) == find(fa,pos2)) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0; } /* 8 6 0 1 0 2 2 3 2 4 5 6 6 7 */

路径优化

#include<iostream> #include<algorithm> #include<vector> using namespace std; const int N = 1e5+10; int n,m; int fa[N]; void set(int u,int v) { fa[v] = u; } int find(int fa[],int i) { int t = i; while(fa[t] != -1) { t = fa[t]; } while(i != fa[i]) { int a = i; i = fa[i]; fa[a] = t; } return t;//返回的是这个节点所在的树的根节点的下标 } int main(void) { cin >> n >> m; for(int i = 0 ; i < n ; i++)//以0为序号 fa[i] = -1; for(int i = 1 ; i <= m ; i++) { int u,v; cin >> u >> v; set(u,v); } for(int i = 0 ; i < n ; i++) cout << fa[i] << " "; int pos1,pos2;//输入像查询节点是否在同一个集合 cin >> pos1 >> pos2; if(find(fa,pos1) == find(fa,pos2)) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0; } /* 8 6 0 1 0 2 2 3 2 4 5 6 6 7 */