题目描述
解题思路
参考https://www.acwing.com/solution/content/88414/
图是一个有且仅有一个环的连通图，实则上就是基环树 要满足两条性质 1.连通 2.点数n = 边数m
TIPS:连通图是一棵树的形式，m = n - 1,但是题目有且仅有一个环，所以需要m = n
代码
cpp
#include <bits/stdc++.h>
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) puts("NO");
else
{
for (int i = 1; i <= n; i++) p[i] = i; // 初始化集合
int cnt = n; // 记录集合数量
while (m--)
{
int a, b;
cin >> a >> b;
if (find(a) != find(b))
{
cnt--;
p[find(a)] = p[find(b)];
}
}
if (cnt == 1) puts("YES"); // 最后只剩下一个集合，说明是一个连通图
else puts("NO");
}
return 0;
}
