[Description]
Teoy最近迷上了阿里巴巴面向网商和中小企业主开发的BNS(Business Network Service)网站“来往”(www.laiwang.com),在那里他可以结交生意上的朋友,包括上游供应商以及下游的客户。随着业务的
扩大,Teoy迫切想认识自己好友列表之外的更多的同行。他提出这样一个问题,给出任意的A和B,他想知
道在“来往”上A能不能间接认识到B。
[Input]
一共有 T 组测试数据。每组数据第一行为三个整数 n,m 和 q,表示人数,给出的关系数和询问数。
接下来共 n 行,每行 2 个整数 x 和 y。表示 x 和 y 认识。
接下来 q 行,表示 q 组询问,q 行每行 2 个整数 x 和 y,表示询问 x 和 y 能否间接认识。
0<t<=100
0<n,m,q<=200
[Output]
对每组数据,给出 q 行,每行分别是“Yes”和“No”,分别回答 x 和 y 是否认识或间接认识。
[Sample Input]
2
3 2 2
1 2
1 3
2 3
1 2
5 3 1
2 3
1 2
3 4
1 4
[Sample Output]
Yes
Yes
Yes
[Source]
3230391@BUPTACM
思路:
并查集(可能是我水过最多的算法)
代码:
#include<iostream> using namespace std; int father[205]; int find_father(int x) { if(x!=father[x]) return find_father(father[x]); return x; } void union_set(int a,int b) { int father_a = find_father(a); int father_b = find_father(b); if(father_a!=father_b) father[father_a] = father_b; } int main() { int t; scanf("%d",&t); while(t--) { int n,m,q,a,b; scanf("%d %d %d",&n,&m,&q); for(int i=1;i<=n;i++) father[i] = i; for(int i=0;i<m;i++) { scanf("%d %d",&a,&b); union_set(a,b); } for(int i=0;i<q;i++) { scanf("%d %d",&a,&b); if(find_father(a)==find_father(b)) printf("Yes\n"); else printf("No\n"); } } }
相关推荐
BOJ的题目1023. Ancient Keyboard解法 源代码
boj 上08 09 年复试模拟题的答案
JAVA_BOJ
boj:算法
Algorithm-BOJ.zip,BekJon在线法官(Java,Kotlin,SWIFT)和PS路线图,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
BOJ
Algorithm-BOJ-PSJ.zip,Baykon在线判断JAVA问题解决方法(第二章),算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Algorithm-BOJ-AutoCommit.zip,当您解决baekjoon online judge的问题时,它会自动提交并推送到远程存储库。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Algorithm-boj-auto-submit.zip,日本央行cli提交脚本,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
资源分类:Python库 所属语言:Python 资源全名:boj-0.0.1.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
通过这本图画书展示您的创造力,其中包括Boj和朋友。 一本有趣的,全数字化且可重复使用的着色书,可用于 通过这本图画书展示您的创造力,其中包括Boj和朋友。 一本有趣的全数字可重复使用的图画书,专为孩子,父母...
解决问题 Boj.kr
欢迎来到PS_BOJ 이곳은... J이한BOJ문제들의AC코드들이입니다。 안내 :check_mark: C ++ Python으로풀이합니다。 :check_mark: ++ C ++풀이하며 long long 필요하거나으으으으으으으으으끔씩만끔씩만끔씩만끔씩만...
BOJ:日本央行