# 0ms Beat 100% Java, Just use a counter

1. There should be exactly n-1 edges
2. Use a counter to track if there are cycles and disconnections
``````public class Solution {
public boolean validTree(int n, int[][] edges) {
if(edges.length != n-1){
return false;
}
boolean[] map = new boolean[n];
Arrays.fill(map, false);
int cnt = 0;
for(int i = 0; i < edges.length; ++i){
int[] tmp = edges[i];
if(map[tmp[0]] && map[tmp[1]]){  // connect 2 known nodes, subtract 2 to remember it
cnt -= 2;
}
else if(!map[tmp[0]] && !map[tmp[1]]){  // connect 2 unknown nodes, add 1 to remember it
cnt += 1;
}
if(cnt < 0){   // connect 2 known nodes, not enough pairs of unknown nodes. There is cycle
return false;
}
map[tmp[0]] = true; // mark nodes to known
map[tmp[1]] = true; // mark nodes to known
}
return cnt == 0 || cnt == 1;  // if cnt > 1, there are disconnections
}
}``````

• @qjwzyy It think this doesn't work on test case:

5
[[0,1],[4,2],[2,3],[2,4]]

• @jade86 It assumes no duplicate edges in the input.

• @liyun1988 Hi, thanks for pointing that out. There is a typo to my example, the example that I wanted to mention is

5
[0,1] [4,2] [2,3] [3,4]

This seems to give a count of 1 + 1 - 2 = 0 in the end but it is not a tree.

• @jade86 Yep. I just realized that too. I found it fails the case 6
[[0, 1], [2,3], [4,5], [0,2], [2, 4]], which is similar to yours.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.