问题1382--图中的项链

1382: 图中的项链

时间限制: 1 Sec  内存限制: 128 MB
提交: 71  解决: 35
[提交] [状态] [讨论版] [命题人:]

题目描述

一个无向图中的项链,是由一系列圈组成,C1,C2,……,Ck(K>=1),并且符合如下规定: 
1. 任何两个圈都没有公共边; 
2. 任意两个相邻的圈有且仅有一个公共点; 
3. 任意两个不相邻的圈没有公共点。 
4. 任意一个点,至多只能出现在一个圈中一次。 
现在要求一个从S到T的项链,C1,C2,……,Ck(K>=1),其中S属于C1,T属于Ck。 
给定一个无向图,以及两个点S和T,问是否存在从S到T的项链。 
题目本质是求S到T,不经过桥是否能到达

输入

第一行一个整数Case(Case<=10)表示测试数据组数。 
每组测试数据第一行两个整数N,M N (2<=N<=10, 000) (1<=M<=100, 000)分别表示无向图中点的数目和边的数目。 
接下来M行,每行两个整数A和B(1<=A B<=N,A不等于B)表示有一条无向边从A到B。 
最后两个整数S和T(1<=S T<=N,S不等于T) 

输出

共Case行,输出”YES”或”NO”,表示是否存在从S到T的项链。

样例输入 Copy

3
3 3 
1 2 
2 3
3 1 
1 3 
4 5 
1 2 
2 3 
1 3 
3 4 
3 4 
1 4 
4 5 
1 2 
1 2 
2 3 
3 4 
3 4 
1 4

样例输出 Copy

YES
YES
NO

来源/分类