图中的环

给定一个 $n$ 个点 $m$ 条边的无向图。

点的编号从 $1$ 到 $n$。

图中不含重边和自环。

请你对给定图进行判断，如果该图是一个有且仅有一个环的连通图，则输出 YES ，否则输出 NO 。

输入格式

第一行包含两个整数 $n,m$。

接下来 $m$ 行，每行包含两个整数 $a,b$，表示点 $a$ 和点 $b$ 之间存在一条无向边。

输出格式

如果该图是一个有且仅有一个环的连通图，则输出 YES ，否则输出 NO 。

数据范围

前三个测试点满足 $1 \leq n \leq 10$。
所有测试点满足 $1 \leq n \leq 100$，$0 \leq m \leq \frac{n \left( n?1 \right)}{2}$，$1 \leq a,b \leq n$。

输入样例1：

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

输出样例1：

YES

输入样例2：

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

输出样例2：

NO

解题思路

　　图是连通的，而且有且只有一个环，那么可以想象一下，这个图有一个环，环上挂着一堆树。这种图就是基环树。

　　一个图是基环树的充分必要条件是：图是连通的、边的数量等于点的数量。

　　因此问题就变成了判断一个图是否为基环树。

　　首先先判断边数是否等于点数，再判断图是否连通。判断图的连通性可以用并查集或dfs。

　　并查集做法：

 1 #include 
 2 #include 
 3 using namespace std;
 4 
 5 const int N = 110;
 6 
 7 int fa[N];
 8 
 9 int find(int x) {
10     return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
11 }
12 
13 int main() {
14     int n, m;
15     scanf("%d %d", &n, &m);
16     if (m != n) {
17         printf("NO");
18         return 0;
19     }
20     
21     for (int i = 0; i <= n; i++) {
22         fa[i] = i;
23     }
24     
25     int cnt = n;
26     while (m--) {
27         int a, b;
28         scanf("%d %d", &a, &b);
29         if (find(a) != find(b)) {
30             fa[find(a)] = find(b);
31             cnt--;
32         }
33     }
34     
35     printf("%s", cnt == 1 ? "YES" : "NO");
36     
37     return 0;
38 }

　　dfs做法：

 1 #include 
 2 #include 
 3 #include 
 4 using namespace std;
 5 
 6 const int N = 110, M = N << 1;
 7 
 8 int head[N], e[M], ne[M], idx;
 9 bool vis[N];
10 int last = -1;
11 
12 void add(int v, int w) {
13     e[idx] = w, ne[idx] = head[v], head[v] = idx++;
14 }
15 
16 void dfs(int src, int pre) {
17     vis[src] = true;
18     for (int i = head[src]; i != -1; i = ne[i]) {
19         if (e[i] != pre && !vis[e[i]]) dfs(e[i], src);
20     }
21 }
22 
23 int main() {
24     int n, m;
25     scanf("%d %d", &n, &m);
26     if (m != n) {
27         printf("NO");
28         return 0;
29     }
30     
31     memset(head, -1, sizeof(head));
32     while (m--) {
33         int v, w;
34         scanf("%d %d", &v, &w);
35         add(v, w), add(w, v);
36     }
37     
38     dfs(1, -1);
39     
40     int cnt = 0;
41     for (int i = 1; i <= n; i++) {
42         if (vis[i]) cnt++;
43     }
44     printf("%s", cnt == n ? "YES" : "NO");
45     
46     return 0;
47 }

参考资料

　　AcWing 4216. 图中的环（AcWing杯 - 周赛）：https://www.acwing.com/video/3690/