Задача
Неориентированный граф без петель и кратных ребер задан матрицей смежности. Определить, является ли этот граф деревом.
Входные данные
Первая строка содержит количество вершин графа $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] |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
import java.util.Scanner; import java.util.ArrayList; class Main { private static void dfs(int v, int p, ArrayList<ArrayList<Integer>> g , int[] A) { A[v]++; if (A[v]>1) return; for (int i=0; i<g.get(v).size(); i++) { if (g.get(v).get(i)!=p) dfs(g.get(v).get(i), v, g, A); } } public static void main (String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] A = new int[n]; ArrayList<ArrayList<Integer>> g = new ArrayList<ArrayList<Integer>>(); for (int i=0; i<n; i++) { ArrayList<Integer> r = new ArrayList<Integer>(); for (int j=0; j<n; j++) { int a = scanner.nextInt(); if (a==1) { r.add(j); } } g.add(r); } int t=0; dfs(0, -1, g, A); for (int i=0; i<n; i++) { if (A[i]!=1) { t++; break; } } if (t!=0) System.out.print("NO"); else System.out.print("YES"); } } |
Решение задачи
Считываем граф в ArrayList<ArrayList>. Далее выбираем любую вершину и запускаем из нее своего рода dfs. Заключается он в том, что мы идем к потомкам текущей вершины, попутно смотря были ли мы здесь. Если были, завершаем процесс, так как мы нашли цикл (граф, содержащий цикл, не является деревом). При этом мы не идем от потомка к предку. В конце проверяем обошли ли мы все вершины и не встречались ли нам циклы.