4216 图中的环（基环树）

87 阅读 0 评论 58 点赞

我是靠谱客的博主壮观百合，这篇文章主要介绍4216 图中的环（基环树），现在分享给大家，希望可以做个参考。

1. 问题描述：

给定一个 n 个点 m 条边的无向图。点的编号从 1 到 n。图中不含重边和自环。请你对给定图进行判断，如果该图是一个有且仅有一个环的连通图，则输出 YES，否则输出 NO。

输入格式

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

输出格式

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

数据范围

前三个测试点满足 1 ≤ n ≤ 10。
所有测试点满足 1 ≤ n ≤ 100，0 ≤ m ≤ n(n − 1) / 2，1 ≤ a，b ≤ 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
来源：https://www.acwing.com/problem/content/description/4219/

2. 思路分析：

首先我们需要分析一下满足题目要求的图有什么性质，可以发现首先需要连通，连通那么就一定存在一棵生成树，因为只有一个环所以这种图是环上挂着一堆树，由这个特点可以知道满足题目要求的这种图属于基环树，然后我们看一下基环树有什么特点，可以发现当一棵树是基环树的时候有两个特点：① 连通图；② m = n；并且当图满足特点①②的时候那么这种图属于基环树，所以这两个条件属于充分必要条件，因为当图连通的时候一定存在一棵生成树，而不管我们在生成树哪两个节点添加一条边最终都只有一个环，所以m = n，所以满足这两个特点的图是基环树；我们可以判断m是否等于n，如果m != n说明一定不是基环图，然后判断所有点是否在同一个集合中，判断所有点是否在同一个集合可以使用并查集进行判断：

3. 代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from typing import List


class Solution:
    # 并查集的find操作, 查找节点x的父节点, 查找节点的时候进行路径压缩
    def find(self, x: int, p: List[int]):
        if p[x] != x: p[x] = self.find(p[x], p)
        return p[x]

    def process(self):
        n, m = map(int, input().split())
        # n != m的时候说明不是基环图
        if n != m:
            print("NO")
            return
        # 使用并查集判断是否连通, p为并查集
        p = [i for i in range(n + 10)]
        res = n
        for i in range(m):
            a, b = map(int, input().split())
            fa, fb = self.find(a, p), self.find(b, p)
            # 当前两个点不在同一个集合那么合并这两个点
            if fa != fb:
                p[fa] = fb
                res -= 1
        # 说明所有点不是在同一个集合
        if res == 1:
            print("YES")
            return
        else:
            print("NO")
            return


if __name__ == '__main__':
    Solution().process()