Check if given graph is tree or not

The problem, simply

You get n dots numbered 0 to n - 1 and a list of lines, each line joining two dots. Lines go both ways. Answer true if this drawing is a tree.

A drawing is a tree when two things hold:

1. It is connected: you can walk from any dot to any other dot along the lines.
2. It has no loop: you can never walk in a circle and come back without using a line twice.

A handy fact: a tree with n dots always has exactly n - 1 lines. And if you already have n - 1 lines, then "no loop" and "connected" become the same thing, so checking one of them is enough.

A story to remember it

Picture it

Examples

Way 1: the simple way

Build a list of neighbors for every dot. Walk from dot 0 with a deep dive, and remember who you came from. If you ever reach a dot you have already seen, and it is not the dot you came from, you found a loop. At the end, check that every dot was reached.

1. If the number of lines is not n - 1, answer false.
2. Build the neighbor lists.
3. Dive from dot 0. Seeing an old dot that is not your parent means a loop.
4. If some dot was never reached, the drawing is not connected.

import java.util.*;

class Solution {
    public boolean isTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        List<List<Integer>> nbrs = new ArrayList<>();
        for (int i = 0; i < n; i++) nbrs.add(new ArrayList<>());
        for (int[] e : edges) {
            nbrs.get(e[0]).add(e[1]);
            nbrs.get(e[1]).add(e[0]);
        }
        boolean[] seen = new boolean[n];
        if (hasLoop(0, -1, nbrs, seen)) return false;
        for (boolean s : seen) if (!s) return false;   // someone was never reached
        return true;
    }

    private boolean hasLoop(int dot, int from, List<List<Integer>> nbrs, boolean[] seen) {
        seen[dot] = true;
        for (int next : nbrs.get(dot)) {
            if (!seen[next]) {
                if (hasLoop(next, dot, nbrs, seen)) return true;
            } else if (next != from) {
                return true;                            // an old dot that is not my parent
            }
        }
        return false;
    }
}

How long it takes: every dot and every line is looked at a couple of times, O(V + E). Extra room: the neighbor lists hold every line twice, O(V + E).

Way 2: the clever way

Play the captain game, which is called union find. We never build neighbor lists. We only keep, for each dot, who it follows.

1. If the number of lines is not n - 1, answer false.
2. Every dot starts as its own captain.
3. For each line, find the captain of both ends. Same captain means a loop: answer false.
4. Otherwise join the teams. The smaller team's captain follows the bigger team's captain.
5. If all lines are used without a loop, answer true. With n - 1 lines and no loop, everything is connected for sure.

class Solution {
    private int[] boss, size;

    private int find(int x) {
        if (boss[x] != x) boss[x] = find(boss[x]);   // shortcut straight to the captain
        return boss[x];
    }

    public boolean isTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        boss = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) { boss[i] = i; size[i] = 1; }
        for (int[] e : edges) {
            int a = find(e[0]), b = find(e[1]);
            if (a == b) return false;                 // same team: this line makes a loop
            if (size[a] < size[b]) { int t = a; a = b; b = t; }
            boss[b] = a;                              // smaller team follows the bigger one
            size[a] += size[b];
        }
        return true;   // n - 1 lines and no loop means connected
    }
}

How long it takes: each line costs two find calls. With shortcuts and size joining, a find is almost free (the inverse Ackermann function, below 5 for any real input), so O(V + E). Extra room: two arrays of size n, O(V).

Watch out for

• In the deep dive, the line back to your parent is not a loop. Remember where you came from. (If the same pair of dots has two lines, that is a real loop, and checking the parent by dot number misses it. Here the "everyone reached" check still catches it, because a doubled line leaves too few lines to connect all the dots.)
• Forgetting dots with no lines at all. They never show up in the line list, but they make the drawing disconnected.
• Recursion depth. A long chain of 100,000 dots can overflow the stack in the deep dive. Union find has no such problem if find is written with a loop.

What interviewers ask next

• Why does n - 1 lines plus no loop mean connected? Each line that joins two different teams lowers the team count by one. n - 1 such joins take n teams down to 1.
• Count the separate pieces of a drawing? Run the same captain game and count successful joins: pieces = n - joins.
• Find the extra line that makes the loop? Return the first line whose two ends already share a captain. That is LeetCode 684, Redundant Connection.
• Lines with one direction only? Then a tree needs one root that reaches everyone, and every other dot has exactly one incoming line. That is LeetCode 685.

Remember this

Grown-up words: the dots are vertices, the lines are edges, the drawing is an undirected graph, the captain game is union find (disjoint set union), the shortcut is path compression, and joining the smaller team to the bigger one is union by size.