博文中会简要介绍Leetcode P0261题目分析及解题思路。
“Graph Valid Tree”是一道中等难度的题目，依据题目要求，我们可以利用深度优先搜索或者广度优先搜索来判断图G中是否存在环，或者是否存在非连通的部分。
You have a graph of n nodes labeled from
0ton - 1. You are given an integer n and a list of edges whereedges[i] = [ai, bi]indicates that there is an undirected edge between nodesaiandbiin the graph.Return
trueif the edges of the given graph make up a valid tree, andfalseotherwise.
首先需要做的是将给定的边数组转化为邻接表或邻接矩阵，这里我将其转换为邻接表。然后利用搜索算法检测环和连通分量。这里使用深度优先搜索更为简单。
检测环只需要关注下一个要访问的结点是否已经被访问过了，如果这个结点已经被访问过了，且不是当前结点上一个访问的结点（即不是“来时”的结点），那么说明有环。
检测连通分量只需要任取某一个结点为起点进行深度优先搜索，如果搜索结束后访问的结点数目等于给定的结点数目，说明图G是连通图，否则不是连通图，也显然不可能是树结构。
以下是Java的题解代码实现。
class Solution {
public boolean validTree(int n, int[][] edges) {
Map<Integer, List<Integer>> adjList = new HashMap<>();
for (int[] e: edges) {
int u = e[0], v = e[1];
if (!adjList.containsKey(u)) {
adjList.put(u, new ArrayList<>());
}
if (!adjList.containsKey(v)) {
adjList.put(v, new ArrayList<>());
}
adjList.get(u).add(v);
adjList.get(v).add(u);
}
int count = this.dfs(0, 0, new boolean[n], adjList);
return !(this.hasCycle || (count != n));
}
private boolean hasCycle = false;
private int dfs(int u, int p, boolean[] visited, Map<Integer, List<Integer>> edges) {
visited[u] = true;
int count = 1;
for (int v: edges.getOrDefault(u, new ArrayList<>())) {
if (!visited[v]) {
count += this.dfs(v, u, visited, edges);
}
else {
this.hasCycle = (this.hasCycle || (v != p));
}
}
return count;
}
}
以下是C++的题解代码实现。
class Solution {
public:
bool validTree(int n, vector<vector<int>>& edges) {
unordered_map<int, vector<int>> adj_list;
for (vector<int> e: edges) {
int u = e[0], v = e[1];
adj_list[u].push_back(v);
adj_list[v].push_back(u);
}
bool cycling = false;
vector<bool> visited(n, false);
int count = _Dfs(0, 0, visited, adj_list, cycling);
return !(cycling || (count != n));
}
private:
int _Dfs(int u, int p, vector<bool> &visited, unordered_map<int, vector<int>> &edges, bool &cycling) {
visited[u] = true;
int count = 1;
for (int v: edges[u]) {
if (!visited[v]) {
count += _Dfs(v, u, visited, edges, cycling);
}
else {
cycling = (cycling || (v != p));
}
}
return count;
}
};