Catch
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 859Accepted Submission(s): 432
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
先开始没想清楚,后来看了下别人的思路
发现只要判断一下连通性和二分图就可以了的说。。
唉。。我的图论太烂了。。
我的代码:
分享到:
相关推荐
ACM/ICPC 2010年多校联合第十场第九题的解题报告及代码,AC代码有三个,最好的是src
HDU2013暑期多校联合训练第一场0723-解题报告和标程
2017hdu多校联合训练第一场标程及数据
HDU图论题目分类
(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数
2014 Multi-University Training Contest 1多校联合赛标程和部分数据。
2019 Multi-University Training Contest 4(2019hdu多校第五场数据与标程),欢迎大家下载
杭电ACM课件2014版之(HDUACM2010版_13)二分匹配及其应用
2019 Multi-University Training Contest 4(2019hdu多校第六场数据与标程)
图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个...
此程序为hdu的acm2010题,就是解决水仙花数问题
HDUACM2010版_14)Hash及应用HDUACM2010版_14)Hash及应用HDUACM2010版_14)Hash及应用HDUACM2010版_14)Hash及应用
HDU2000至2099题的题目以及AC代码(含思路) 适合刚刚接触ACM的同学哦~ emmmm凑字
有2019 Multi-University Training Contest 4,hdu多校第四场的题解,数据标程,有需要的可以下载哦
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
此乃2012多校联赛第五场的题目+数据+题解+标程
HDU1059的代码
hdu1001解题报告