e-olymp 977. Дерево?

Задача

Неориентированный граф без петель и кратных ребер задан матрицей смежности. Определить, является ли этот граф деревом.

Входные данные

Первая строка содержит количество вершин графа $n \left (1 \leq n \leq 100 \right).$ Далее записана матрица смежности размером $n × n$, в которой $1$ обозначает наличие ребра, $0$ — его отсутствие. Матрица симметрична относительно главной диагонали.

Выходные данные

Выведите сообщение YES, если граф является деревом, и NO в противном случае.

Тесты

Входные данные Выходные данные
[latex]3 \\ 0 \ 1 \ 0 \\ 1 \ 0 \ 1 \\ 0 \ 1 \ 0[/latex] [latex]YES[/latex]
[latex]2 \\ 0 \ 1 \\ 1 \ 0[/latex] [latex]YES[/latex]
[latex]4 \\ 0 \ 0 \ 0 \ 1 \\ 0 \ 0 \ 1 \ 0 \\ 0 \ 1 \ 0 \ 0 \\ 1 \ 0 \ 0 \ 0[/latex] [latex]NO[/latex]
[latex]1 \\ 0[/latex] [latex]YES[/latex]

Код программы

Решение задачи

Считываем граф в ArrayList<ArrayList>. Далее выбираем любую вершину и запускаем из нее своего рода dfs. Заключается он в том, что мы идем к потомкам текущей вершины, попутно смотря были ли мы здесь. Если были, завершаем процесс, так как мы нашли цикл (граф, содержащий цикл, не является деревом). При этом мы не идем от потомка к предку. В конце проверяем обошли ли мы все вершины и не встречались ли нам циклы.

Ссылки

Условие задачи на e-olymp
Код решения

e-olymp 4000. Обход в глубину

Задача

Дан неориентированный невзвешенный граф, в котором выделена вершина. Вам необходимо найти количество вершин, лежащих с ней в одной компоненте связности (включая саму вершину).

Входные данные

В первой строке содержится количество вершин графа $n$ и выделенная вершина $s$ $\left (1 \leq s \leq n \leq 100 \right).$ В следующих n строках записано по n чисел — матрица смежности графа, в котрой цифра «$0$» означает отсутствие ребра между вершинами, а цифра «$1$» — его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.

Выходные данные

Выведите искомое количество вершин.

Тесты

Входные данные Выходные данные
3 1
0 0 1
0 0 0
1 0 0
2
4 2
0 1 0 0
1 0 0 1
0 0 0 1
0 1 1 0
4
6 2
0 1 0 0 0 1
1 0 0 0 0 1
0 0 0 1 1 0
0 0 1 0 0 0
0 0 1 0 0 0
1 1 0 0 0 0
3
4 2
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1
5 3
0 1 0 0 1
1 0 1 0 1
0 1 0 1 0
0 0 1 0 1
1 1 0 1 0
5

Код программы

Решение задачи

Для хранения графа воспользуемся списками смежности. Реализуем стандартный поиск в глубину. Пусть $c$ количество вершин в компоненте графа. Изначально $c = 0.$ При посещении очередной, не посещенной ранее вершины, значение $c$ увеличивается на один. Таким образом, при полном обходе компоненты графа, $c$ будет искомым числом.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone