«Олимпиадное программирование» - курс для начинающих

Граф называется деревом, если он связный и не имеет циклов.
Граф называется связным, если любые две его вершины связны, т.е. граф содержит ровно одну компоненту связности.

Следствие: каждое дерево с n вершинами имеет в точности n-1 ребро.

С++ bfs (breadth-first search)

С++ dfs (depth-first search)