#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
*/
