题目描述：
给定一个 n 个点 m 条边的无向图。
点的编号从 1 到 n。
图中不含重边和自环。
请你对给定图进行判断，如果该图是一个有且仅有一个环的连通图，则输出 YES，否则输出 NO。
输入格式
第一行包含两个整数 n,m。
接下来 m 行，每行包含两个整数 a,b，表示点 a 和点 b 之间存在一条无向边。
输出格式
如果该图是一个有且仅有一个环的连通图，则输出 YES，否则输出 NO。
数据范围
前三个测试点满足 $ 1\le n\le 10 $ 。
所有测试点满足 $ 1 \le n \le 100 $ 。
输入样例1：
1
2
3
4
5
6
7
| 6 6
6 3
6 4
5 1
2 5
1 4
5 4
|
输出样例1：
输入样例2：
输出样例2：
题解：
求环的数目可以直接 dfs，无向图 dfs 会返回双倍的环数，因为每个环可以顺时针逆时针遍历两次。
判断连通直接可以遍历 vis 数组，判断访问过的点数。
代码：
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
struct Edge
{
int u, v, next;
} edge[maxn * maxn];
int head[maxn], cnt;
inline void addEdge(int u, int v)
{
edge[++cnt] = {u, v, head[u]};
head[u] = cnt;
}
bool vis[maxn];
int dfs(int u, int fa)
{
if (vis[u])
return 1;
vis[u] = true;
int ans = 0;
for (int i = head[u]; i; i = edge[i].next)
{
int v = edge[i].v;
if (v == fa)
continue;
ans += dfs(v, u);
}
return ans;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1, u, v; i <= m; i++)
{
cin >> u >> v;
addEdge(u, v);
addEdge(v, u);
}
bool flag = (dfs(1, -1) / 2 == 1);
for (int i = 1; i <= n; i++)
{
if (vis[i] == false)
{
flag = false;
break;
}
}
if (flag)
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
return 0;
}
|