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
.
Solution 1: Build the Graph then DFS
public class Solution {
public boolean validTree(int n, int[][] edges) {
List<Integer>[] adj=new List[n];
for (int i=0; i<n; i++) adj[i]=new LinkedList<>();
for (int i=0; i<edges.length; i++) {
adj[edges[i][0]].add(edges[i][1]);
adj[edges[i][1]].add(edges[i][0]);
}
boolean[] marked=new boolean[n];
boolean[] hasCycle=new boolean[1];
dfs(adj,-1,0,hasCycle,marked);
for (int v=0; v<n; v++) {
if (!marked[v]) return false;
}
return !hasCycle[0];
}
private void dfs(List<Integer>[] adj, int s, int v, boolean[] hasCycle, boolean[] marked) {
marked[v]=true;
for (int w: adj[v]) {
if (hasCycle[0]) return;
else if (w!=s) {
if (!marked[w]) dfs(adj,v,w,hasCycle,marked);
else hasCycle[0]=true;
}
}
}
}
Solution 2: Uni-Find
public class Solution {
public boolean validTree(int n, int[][] edges) {
int[] nums=new int[n];
Arrays.fill(nums,-1);
for (int[] edge: edges) { //check loop
int x=edge[0], y=edge[1];
int c1=0, c2=0;
while (nums[x]!=-1) {
x=nums[x];
c1++;
}
while (nums[y]!=-1) {
y=nums[y];
c2++;
}
if (x==y) return false;
if (c1>c2) nums[y]=x;//connected small part to big part
else nums[x]=y;
}
int count=0; //check all connected, nums of -1 is nums of cc
for (int i=0; i<n; i++) {
if (nums[i]==-1 && ++count>1) return false;
}
return true;
}
}
没有评论:
发表评论