nowcoder 2020/6/20 L-小梁的道馆

小梁变强之后决定建设自己的道馆，她特别喜欢去其他的道馆串门。
但是有些道馆之间没有道路连通，于是小梁想知道自己能不能去她想去的道馆，
你能帮她写一个程序来查询两个道馆之间是否互相存在道路联通吗；
如果存在输出“YES”，反之输出“NO”。

示例1
输入

4 2 2
1 3
4 3
1 2
3 4

输出

NO
YES

图论部分？用并查集可解。做了这个后发现相关题目非常多。
之前做的相关的题目：小希的迷宫
比这题难一些，还需要判断是否存在多个祖先（集合？）

本题完整代码：

#include<bits/stdc++.h>
using namespace std;

int f[1005];
int find(int k)
{
	if(f[k]==k)return k;
	else return f[k]=find(f[k]);
}
void link(int a,int b)
{
	if(find(a)!=find(b))f[find(b)]=find(a);
}

int main()
{
	ios::sync_with_stdio(false);
	int n,m,t;
	int a,b;
	cin>>n>>m>>t;
	for(int i=0;i<1005;i++)f[i]=i;
	while(m--){
		cin>>a>>b;
		link(a,b);
	}
	while(t--){
		cin>>a>>b;
		//cout<<find(a)<<" "<<find(b)<<endl;
		if(find(a)==find(b))cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}

nowcoder 2020/6/20 L-小梁的道馆

原文：https://www.cnblogs.com/LiangYC1021/p/13169986.html