图中的环
图中的环
2024.7.17
AcWing 4216. 图中的环：https://www.acwing.com/file_system/file/content/whole/index/content/4187139/
一、题目
二、题解
1. 基环树
如下图所示，基环树中只有一个环，且整个图是联通的。可以推断出它的性质：连通图；节点数=边数。
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;
}