# My solution without using graph traversal

• I just determined whether the graph is a tree by

1. whether it has correct number of edges

2. whether it has any isolated edge(when n >2)

3. whether it has any isolated vertex(when n > 1)

Not sure if my strategy is correct. But this strategy passed the test

Would really appreciate if anyone could find an exception. Thanks!!

class Solution {
public:
bool validTree(int n, vector<pair<int, int>>& edges) {
if (edges.size() != n-1) return false;
int vertexes[n];
fill_n(vertexes, n, 0);
for (pair<int, int> &e : edges) {
vertexes[e.first] ++;
vertexes[e.second] ++;
}
/* Check if the graph has any isolated edge /
for (pair<int, int> &e : edges) {
if (vertexes[e.first] == 1 && vertexes[e.second] == 1 && n > 2) {
return false;
}
}
/
Check if the graph has any isolated vertex */
for (int v = 0; v < n; v++) {
if (vertexes[v] == 0 && n != 1) return false;
}
return true;
}
};

• Not sure if my strategy is correct. But this strategy passed the test
Would really appreciate if anyone could find an exception.

Here's one:

n = 6;
edges = {{0, 1}, {1, 2}, {2, 0}, {3, 4}, {4, 5}};

• Thanks Stefan. I have just added this test case.

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