Problem7504--无向图中是否有环

7504: 无向图中是否有环

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MiB

Description

给定一个无向图,请判断这个图中是否有环
注:这个图未必是连通图

Input

第一行:两个整数n m,空格分开,n表示顶点数,m表示边数(1<=n<=100, 1<=m<=1000)
以下m行,每行两个整数f,t,表明从顶点f到顶点t有一条边

Output

如果图中有环,输出:yes
如果图中无环:输出:no

Sample 1 Input

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

Sample 1 Output

yes

HINT

可用方法:
1. 深搜:看是否访问已经访问过的点
2. 广搜:通过看各点层次判断有无回边
3. 类似拓扑排序:每次删除度为1的点
4. 并查集:如果要合并的两个顶点已经属于一个集合,那么存在环

Source/Category

图论