Exercise 1 solution

    def components(g):
        seen = set()
        result = []
        for start in g:
            if start in seen:
                continue
            seen.add(start)
            stack, comp = [start], []
            while stack:
                cur = stack.pop()
                comp.append(cur)
                for nb in g[cur]:
                    if nb not in seen:
                        seen.add(nb)
                        stack.append(nb)
            result.append(sorted(comp))
        return result

    def has_cycle(g):
        seen = set()
        for start in g:
            if start in seen:
                continue
            seen.add(start)
            stack = [(start, None)]          # (node, node we came from)
            while stack:
                cur, came_from = stack.pop()
                for nb in g[cur]:
                    if nb == came_from:
                        continue             # the edge we just walked along
                    if nb in seen:
                        return True
                    seen.add(nb)
                    stack.append((nb, cur))
        return False

    g = {
        1: [2], 2: [1, 3], 3: [2],
        4: [5], 5: [4],
        6: [],
    }
    print(components(g))
    print(has_cycle(g))

    g[3].append(1)
    g[1].append(3)
    print(has_cycle(g))

    print(components({}), has_cycle({}))
    tri = {"x": ["y", "z"], "y": ["x", "z"], "z": ["x", "y"]}
    print(components(tri), has_cycle(tri))

Output:
    [[1, 2, 3], [4, 5], [6]]
    False
    True
    [] False
    [['x', 'y', 'z']] True

Each unvisited node starts a new search, and everything that search reaches
is one component, so a node with no edges is a component of its own. For
cycle detection in an undirected graph, every edge appears twice (once from
each end), so the edge we just walked along must be ignored: we remember the
node we came from. Meeting any other already-seen node means there are two
different routes to it, which is a cycle. The "seen" check is on discovery,
not on removal from the stack, so each node is queued at most once.