Является ли граф деревом — Python — Ответ 16148518
Дан неориентированный невзвешенный граф. Необходимо определить, является ли он деревом.
Входные данные
В первой строке входного файла содержится одно натуральное число N (N ≤ 100) — количество вершин в графе. Далее в N строках по N чисел — матрица смежности графа: в i-ой строке на j-ом месте стоит 1, если вершины i и j соединены ребром, и 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
Мой код (реализован обход по графу в глубину + проверка на наличие петель):
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
n = int(input()) a = [] for i in range(n): a.append(list(map(int, input().split()))) vert = [0] color = [0]*n color[0] = 1 while len(vert) != 0: f = 0 for i in range(n): if a[vert[-1]][i] == 1 and color[i] == 0: vert.append(i) color[i] = 1 f = 1 break if f == 0: vert.pop() k = "YES" for i in color: if i == 0: k = 'NO' for i in range(n): if a[i][i] != 0: k = 'NO' print(k)
Программа не заходит. Есть ощущение, что я что-то не проверила. Где ошибка?
Источник
Является ли граф деревом
Дан неориентированный невзвешенный граф. Необходимо определить, является ли он деревом.
Входные данные
В первой строке входного файла содержится одно натуральное число N (N ≤ 100) — количество вершин в графе. Далее в N строках по N чисел — матрица смежности графа: в i-ой строке на j-ом месте стоит 1, если вершины i и j соединены ребром, и 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
Мой код (реализован обход по графу в глубину + проверка на наличие петель):
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
n = int(input()) a = [] for i in range(n): a.append(list(map(int, input().split()))) vert = [0] color = [0]*n color[0] = 1 while len(vert) != 0: f = 0 for i in range(n): if a[vert[-1]][i] == 1 and color[i] == 0: vert.append(i) color[i] = 1 f = 1 break if f == 0: vert.pop() k = "YES" for i in color: if i == 0: k = 'NO' for i in range(n): if a[i][i] != 0: k = 'NO' print(k)
Источник
Является ли граф деревом — Python — Ответ 16148674
А зачем здесь обход? Если граф с n вершинами является деревом, то у него должно быть n-1 ребро. Считаешь число единиц в верхнем треугольнике матрицы смежности и сравниваешь с n-1:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
n=int(input()) matr=[] for _ in range(n): row=list(map(int,input().split())) matr.append(row) ed=0 for i in range(n-1): for j in range(i+1,n): if matr[i][j] != 0: ed+=1 if ed==n-1: print("YES") else: print("NO")
Определить является ли ненаправленный граф двудольным
Вам дан ненаправленный граф. Определите является ли он двудольным. Граф называется двудольным.
Является ли граф — деревом?
Доброго времени суток. Есть граф, нужно пробежаться по нему в ширину, и если не встретится циклов.
Является ли граф деревом
Суть задачи заключается в том, что нужно проверить граф, является ли он деревом. Граф является.
Определить,является ли граф деревом
Помогите пожалуйста,завтра надо сдать работу. 1.Задано матрицу смежности простого.
Проверить, является ли граф деревом
Добрый день. Нужно проверить, является ли граф деревом с помощью построения его остова поиском в.
Определить, является ли граф деревом
Дан неориентированный граф, список инцидентности. Любым способом нужно определить, является ли он.
Определить, является ли этот граф деревом
Неориентированный граф без петель и кратных ребер задан матрицей смежности. Определить, является ли.
Определить, является ли данный граф деревом
Помогите, пожалуйста, выполнить любой из пунктов "результаты". Создать матрицу смежности вершин.
Графы. Определить, является ли граф деревом
Помогите написать программу,в которой был бы создан граф,все связи считывались бы с файла, и потом.
Определить, является ли заданный граф свободным деревом
не могу справится с заданием по языку LISP, помогите пожалуйста Определить, является ли заданный.
Дан неориентированный граф. Необходимо определить, является ли он деревом
Формат входных данных В первой строке входного файла содержится одно натуральное число N.
Источник