is_tree.py

"""
Дан неориентированный невзвешенный граф.
Необходимо определить, является ли он деревом.

Входные данные
В первой строке входного файла содержится одно натуральное число 𝑁 (𝑁 ≤ 100) - количество вершин в графе.
Далее в 𝑁 строках по 𝑁 чисел - матрица смежности графа: в 𝑖-ой строке на 𝑗-ом месте стоит 1, если вершины 𝑖 и 𝑗 соединены ребром, и 0, если ребра между ними нет.
На главной диагонали матрицы стоят нули.
Матрица симметрична относительно главной диагонали.

Выходные данные
Вывести "YES", если граф является деревом, и "NO" иначе.

Пример:
Входные данные:
6
0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 0
0 0 0 0 0 0

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

Входные данные:
3
0 1 0
1 0 1
0 1 0

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

"""

"""
Теория:
Граф является деревом тогда и только тогда, когда он является связным и не содержит циклов.
"""


def is_cycles(prev_vertex, vertex, visited, adjacency_matrix, n):
    """
    Проверить, содержит ли граф циклы.

    Пример:
    -------
    1 - 2 - 3
    |   |
    4 - 5

    vertex = 1, prev_vertex = None,                     visited = [False, False, False, False, False]
    is_cycles(None, 1, visited, adjacency_matrix, 5)    visited = [True, False, False, False, False]
    is_cycles(1, 2, visited, adjacency_matrix, 5)       visited = [True, True, False, False, False]
    is_cycles(2, 3, visited, adjacency_matrix, 5)       visited = [True, True, True, False, False]
    is_cycles(2, 5, visited, adjacency_matrix, 5)       visited = [True, True, True, False, True]
    is_cycles(5, 4, visited, adjacency_matrix, 5)       visited = [True, True, True, True, True]
    is_cycles(4, 1, visited, adjacency_matrix, 5) – цикл обнаружен, возвращаем True

    prev_vertex - предыдущая вершина
    vertex - номер вершины, с которой начинается обход
    visited - список посещенных вершин
    adjacency_matrix - матрица смежности графа
    n - количество вершин в графе
    """
    # Пометить вершину как посещенную
    visited[vertex] = True

    # Обойти все смежные вершины
    for other_vertex in range(n):
        # Если вершина other_vertex не смежна с vertex или это предыдущая вершина, то пропустить
        if adjacency_matrix[vertex][other_vertex] == 0 or other_vertex == prev_vertex:
            continue

        # Если смежная вершина еще не посещена, то продолжить обход из нее
        if not visited[other_vertex]:
            if is_cycles(vertex, other_vertex, visited, adjacency_matrix, n):
                return True
        # Если смежная вершина уже посещена, то граф содержит циклы
        else:
            return True
    # Вернуть False, если циклов не обнаружено
    return False

def solve():
    # Получить количество вершин в графе
    n = int(input())

    # Получить матрицу смежности графа
    adjacency_matrix = []
    for i in range(n):
        adjacency_matrix.append(list(map(int, input().split())))

    # Количество ребер графа
    edges = 0
    for i in range(n):
        # Матрица симметрична относительно главной диагонали, поэтому достаточно обойти только верхнюю половину
        for j in range(i+1, n):
            if adjacency_matrix[i][j] == 1:  # Если вершины i и j соединены ребром
                edges += 1  # Увеличить количество ребер на 1
    
    # Граф не является деревом, если количество ребер не равно количеству вершин - 1
    if edges != n - 1:
        print("NO")
        return

    # Пометить все вершины как не посещенные
    visited = [False] * n

    # Обойти граф в глубину
    # Если в процессе обхода будет обнаружен цикл, то граф не является деревом
    if not is_cycles(-1, 1, visited, adjacency_matrix, n):
        print("YES")
    else:
        print("NO")  # Граф содержит цикл


# Тестовые данные
# Входные данные:
input_data = """6
0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 0
0 0 0 0 0 0
"""
import sys
from io import StringIO
sys.stdin = StringIO(input_data)

solve()