一、题目

题目链接：https://www.acwing.com/problem/content/description/4219/

给定一个 nn 个点 mm 条边的无向图。

点的编号从 11 到 nn。

图中不含重边和自环。

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

输入格式

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

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

输出格式

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

数据范围

前三个测试点满足 1≤n≤101 \le n \le 10。
所有测试点满足 1≤n≤1001 \le n \le 100，0≤m≤n(n−1)20 \le m \le \frac{n(n-1)}{2}，1≤a,b≤n1 \le a,b \le 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

二、题解

1. 基环树

如下图所示，基环树中只有一个环，且整个图是联通的。可以推断出它的性质：连通图；节点数=边数。

image-20240717211813659

2. 并查集

两个基本操作：

  • 判断两个元素是不是在一个集合中
  • 将两个集合合并

关键函数：

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

三、代码

#include <iostream>

using namespace std;

const int N = 110;

int n, m;
int p[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;
    if (n != m) cout << "NO" << endl;
    else 
    {
        for (int i = 1; i <= n; i ++ )
            p[i] = i;
        int cnt = n; // 存储集合的数量
        for (int line = 0; line < m; line ++ )
        {
            int a, b;
            cin >> a >> b;
            if (find(a) != find(b))
            {
                cnt -- ;
                p[find(a)] = find(b);
            }    
        }
        if (cnt == 1) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}