【CSU - 1004】Xi and Bo(并查集,裸题)

题干:

Bo has been in Changsha for four years. However he spends most of his time staying his small dormitory. One day he decides to get out of the dormitory and see the beautiful city. So he asks to Xi to know whether he can get to another bus station from a bus station. Xi is not a good man because he doesn't tell Bo directly. He tells to Bo about some buses' routes. Now Bo turns to you and he hopes you to tell him whether he can get to another bus station from a bus station directly according to the Xi's information.

Input

The first line of the input contains a single integer T (0<T<30) which is the number of test cases. For each test case, the first contains two different numbers representing the starting station and the ending station that Bo asks. The second line is the number n (0<n<=50) of buses' routes which Xi tells. For each of the following n lines, the first number m (2<=m<= 100) which stands for the number of bus station in the bus' route. The remaining m numbers represents the m bus station. All of the bus stations are represented by a number, which is between 0 and 100.So you can think that there are only 100 bus stations in Changsha.

Output

For each test case, output the "Yes" if Bo can get to the ending station from the starting station by taking some of buses which Xi tells. Otherwise output "No". One line per each case. Quotes should not be included.

Sample Input

3
0 3
3
3 1 2 3
3 4 5 6
3 1 5 6
0 4
2
3 0 2 3
2 2 4
3 2
1
4 2 1 0 3

Sample Output

No
Yes
Yes

解题报告:

   直接并查集就好了。留给学弟做练习用。

AC代码:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
int f[MAX],q[MAX];
int getf(int v) {
	return f[v] == v ? v : f[v] = getf(f[v]);
}
void merge(int u,int v) {
	int t1 = getf(u);
	int t2 = getf(v);
	f[t2] = t1;
}
void init() {
	for(int i = 0; i<=100; i++) {
		f[i] = i;
	}
} 
int main()
{
	int t,m;
	cin>>t;
	while(t--) {
		int st,ed;
		scanf("%d%d",&st,&ed);
		scanf("%d",&m);
		init();
		for(int num,i = 1; i<=m; i++) {
			scanf("%d",&num);
			for(int j = 1; j<=num; j++) {
				scanf("%d",q+j);
			}
			for(int j = 2; j<=num; j++) {
				merge(q[j],q[j-1]);
			}
		}
		if(getf(st) == getf(ed)) puts("Yes");
		else puts("No");
	}


	return 0 ;
}
//12:33-12:40

 

全部评论

相关推荐

门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务