给定从 0 到 n-1 标号的 n 个结点,和一个无向边列表(每条边以结点对来表示),请编写一个函数用来判断这些边是否能够形成一个合法有效的树结构。 编程提示:满足合法有效的树结构的条件是: (1)图的连通分量个数不能大于1 (2)图中不能存在回边(可通过深度优先遍历来检查,如果一个顶点的邻接点之前已被访问过,且超过两个,则说明存在回边) 【输入形式】 顶点数 边数目 边列表完整代码c++
时间: 2024-02-16 21:00:23 浏览: 56
leetcode261. 以图判树
好的,根据你的要求,我可以给出一个完整的C++代码,实现判断无向图是否为树的功能。
```cpp
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 10010;
vector<int> adj_list[MAXN];
bool visited[MAXN];
bool dfs(int node, int parent) {
visited[node] = true;
for (int i = 0; i < adj_list[node].size(); i++) {
int neighbor = adj_list[node][i];
if (!visited[neighbor]) {
if (!dfs(neighbor, node)) {
return false;
}
} else if (neighbor != parent) {
return false;
}
}
return true;
}
bool is_tree(int n, int m, vector<pair<int, int>>& edges) {
// 构建邻接表
memset(visited, false, sizeof(visited));
for (int i = 0; i < MAXN; i++) {
adj_list[i].clear();
}
for (int i = 0; i < m; i++) {
int u = edges[i].first;
int v = edges[i].second;
adj_list[u].push_back(v);
adj_list[v].push_back(u);
}
// 判断连通性
int cnt = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
if (!dfs(i, -1)) {
return false;
}
cnt++;
}
}
if (cnt != 1) {
return false;
}
// 判断是否存在回边
memset(visited, false, sizeof(visited));
if (!dfs(0, -1)) {
return false;
}
for (int i = 0; i < n; i++) {
if (!visited[i]) {
return false;
}
}
return true;
}
int main() {
int n, m;
cin >> n >> m;
vector<pair<int, int>> edges(m);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
edges[i] = {u, v};
}
if (is_tree(n, m, edges)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
return 0;
}
```
以上代码中,我们首先使用邻接表存储图的数据结构,然后进行两次DFS遍历。第一次遍历检查连通性,第二次遍历检查是否存在回边。如果以上两个条件都满足,则输出YES,否则输出NO。
注意:在输入时,每条边都是以顶点对的形式输入的,如 `0 1` 表示一条从0到1的无向边。
阅读全文