Is This Graph a Tree

MediumGraphsUnion findDfs153 tests

You are given n nodes numbered 0 to n - 1 and a list edges. Each edge [u, v] joins nodes u and v. The edges have no direction.

The graph is a tree when both of these are true:

it is connected: you can get from any node to any other node by following edges;
it has no cycle: you cannot leave a node, follow edges without using any edge twice, and come back to the same node.

Return true if the graph is a tree, and false if it is not.

Note

No edge appears twice, and no edge joins a node to itself.
A single node with no edges is a tree.

Hint: a union-find (disjoint set) structure helps. For each edge, if its two nodes are already in the same group, this edge closes a cycle. At the end, check that all nodes are in one group.

Examples

Example 1

Input:: 5, [[0,3],[3,1],[3,4],[4,2]]
Output:: true

Node 3 joins 0, 1 and 4, and node 4 joins 2. Every node can be reached, and there is no way to go in a circle.

Example 2

Input:: 5, [[0,1],[1,2],[2,0],[3,4]]
Output:: false

Nodes 0, 1 and 2 form a cycle, and nodes 3 and 4 cannot be reached from them. The graph has 4 edges, which is n - 1, but it is still not a tree.

Example 3

Input:: 4, [[2,0],[0,3]]
Output:: false

There is no cycle, but node 1 has no edges, so the graph is not connected.

Constraints

1 <= n <= 12
0 <= edges.length <= 15
edges[i] = [u, v] with 0 <= u, v < n and u != v
No edge appears twice ([u, v] and [v, u] count as the same edge).

Run checks your code against the 3 examples. Submit checks it against all 153 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.