Catch

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2816    Accepted Submission(s): 1320

Problem Description

A thief is running away!
We can consider the city where he locates as an undirected graph in which nodes stand for crosses and edges stand for streets. The crosses are labeled from 0 to N–1.
The tricky thief starts his escaping from cross S. Each moment he moves to an adjacent cross. More exactly, assume he is at cross u at the moment t. He may appear at cross v at moment t + 1 if and only if there is a street between cross u and cross v. Notice that he may not stay at the same cross in two consecutive moment.
The cops want to know if there’s some moment at which it’s possible for the thief to appear at any cross in the city.

Input

The input contains multiple test cases:
In the first line of the input there’s an integer T which is the number of test cases. Then the description of T test cases will be given.
For any test case, the first line contains three integers N (≤ 100 000), M (≤ 500 000), and S. N is the number of crosses. M is the number of streets and S is the index of the cross where the thief starts his escaping.
For the next M lines, there will be 2 integers u and v in each line (0 ≤ u, v < N). It means there’s an undirected street between cross u and cross v.

Output

For each test case, output one line to tell if there’s a moment that it’s possible for the thief to appear at any cross. Look at the sample output for output format.

Sample Input

2

3 3 0

0 1

0 2

1 2

2 1 0

0 1

Sample Output

Case 1: YES

Case 2: NO

Hint

For the first case, just look at the table below. (YES means the thief may appear at the cross at that moment)

For the second input, at any moment, there’s at least one cross that the thief can’t reach.

Source

2010 ACM-ICPC Multi-University Training Contest(5)——Host by BJTU

 如果小偷能走一个环,如果这个环是偶数个节点,那么某个节点只能在偶数时刻或者奇数时刻到达;

但是如果这个环是奇数个节点,他既可以在奇数时刻到达又可以在偶数时刻到达;所以这道题就是求是否存在一个奇环;如果存在输出YES,否则NO;

由于二分图中不能含有奇环,所以我们只需用染色法判断是否是二分图即可

我的并查集出了点问题……然后题意问题。。这题head和color必须要memst才能过

然后学了点图论知识

首先,如果小偷有某一个时刻可能出现在所有城市,首先我们一定要确保整个图是连通的,如果整个图不是连通的,那么必然有一些点是一辈子都不可能达到的,辣么我们首先要判连通,判断连通的方法有很多,这里我采用并查集判连通的方法,把所有边都链接起来,最后遍历一遍所有点,如果f【i】==i的i只有一个,也就是说这些个点只有一个祖先,其实也就是说所有的点都在一颗树里边,那么这个图就是连通的、

如果图不是连通的,直接输出NO,那么如果连通怎么继续判断呢?

根据小偷逃跑的独特方式,我们不难想到二分图的相关内容,例如图中这样的一个二分图:

起点假设为1,0时刻只能出现在1,1时刻可能会出现在3和1(出现在1的原因是我可以不跑啊T__T)然后2时刻可能会出现在1、3、5,然后3时刻可能会出现在1 3 5 7,之后无论什么时刻,都是可能出现在1 3 5 7,永远不会出现在2 4 6(另一个集合)。那么相反,如果起点设置为2,我们不难发现在之后的时刻,一定有可能会在某一时刻出现在2、4、6这同集合的点,永远不可能出现在另一个集合1 3 5 7,这些点里边,为什么呢?原因很简单,因为起点出现在二分图某一个集合的点里边,而且整个图满足了二分图的定论。那么如果我们想出现在另外一个集合怎么办呢?

如图就是一种解决方案:

如图是在35之间建立一条边,同理,如果在 5 7之间建立一条边,或者是在1 7之间建立一条边,或者是…………………..总之,在同一个集合里边,建立一条边,使其不满足二分图的情况即可,只要有一条边能够破坏二分图,辣么我们就一定有某一时刻在另一个集合出现,只要在另一个集合里边任意一个点出现了,就像刚刚一样,慢慢蔓延,就会满足在之后的某一时刻小偷有可能出现在所有点。

所以我们解决方法也不难想到BFS二分图染色的方法了,如果满足了二分染色,那么图一定满足二分图,如果不满足二分染色,那么这个图一定不是二分图,也就是输出YES的情况。

最后修改日期:2019年10月21日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。