题目
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.
For example:
Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.
Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
答案
class Solution {
public boolean validTree(int n, int[][] edges) {
boolean[][] matrix = new boolean[n][n];
boolean[] visited = new boolean[n];
boolean ret = false;
for(int i = 0; i < edges.length; i++)
matrix[edges[i][0]][edges[i][1]] = matrix[edges[i][1]][edges[i][0]] = true;
if(!dfs(0, -1, n, visited, matrix)) return false;
for(int i = 0; i < n; i++) {
if (!visited[i]) return false;
}
return true;
}
private boolean dfs(int v, int parent, int n, boolean[] visited, boolean[][] matrix) {
visited[v] = true;
boolean ret = false;
for(int i = 0; i < n; i++) {
if(i == v) continue;
if(matrix[v][i]) {
if(visited[i]) {
if(i != parent) return false;
}
else {
if(!dfs(i, v, n, visited, matrix))
return false;
}
}
}
return true;
}
}
