hello-world00
@hello-world00
Играю с Python,C

В каких еще случаях граф называется ориентированным?

Решаю задачу и не могу придумать тесты для задачи.
Решение такое:
N = int(input())
G = [[0]*N for _ in range(N)]
p = 0
for i in range(N):
  G[i] = list(map(int, input().split()))
  p += sum(G[i])
#if p == 0:print("NO"); exit(); # (Ничего не меняется, будь то YES или NO)

for i in range(N):
  for j in range(N):
    if (i == j and G[i][j] == 1):
      print("NO");exit()
    elif (G[i][j] != G[j][i]):
      print("YES");exit()
print("NO")

Т.е. если у графа есть хоть одно ребро, имеющее направление, то это орграф. Но не проходит 13 тест.
И я не понимаю, будет ли граф ориентированным, если количество вершин <= 1 или количество ребер = 0?
Какие тесты можно придумать?
  • Вопрос задан
  • 112 просмотров
Решения вопроса 2
Griboks
@Griboks
.е. если у графа есть хоть одно ребро, имеющее направление, то это орграф.

Всё правильно.
если количество вершин <= 1 или количество ребер = 0

Количество вершин не может быть 0, т.е., если 0 вершин, то это уже не граф. Количество рёбер может быть любым.
Но не проходит 13 тест.

Забавно, что вы не написали тест №13.
if (i == j and G[i][j] == 1):

Я ничего не понимаю в матрицах смежности, но, возможно, вам стоит перенести G[i][j]==1 во внутрь условия:
for i in range(N):
  for j in range(N):
    if (i == j):
      if (G[i][j] == 1):
          print("NO");exit()
    elif (G[i][j] != G[j][i]):
      print("YES");exit()

p.s.
Естественно, этот код ужасен. Не повторяйте в продакшене.
Ответ написан
SagePtr
@SagePtr
Еда - это святое
Собственно, ошибка будет, если в графе встретится соответствие и этому условию:
if (i == j and G[i][j] == 1):

И этому условию:
elif (G[i][j] != G[j][i]):

В таком случае результат будет зависеть от того, какое из условий встретится раньше.
Первую проверку я бы вообще вынес из вложенного цикла и прогонял бы сначала одиночный цикл в поисках проблем с главной диагональю, а потом уже прогонял двойной цикл в поисках асимметрии, тогда при провале теста диагонали будет явно NO.

Контртест:
0 1
0 1
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы