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

Question

[Hello World]

Решаю задачу и не могу придумать тесты для задачи.
Решение такое:

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?
Какие тесты можно придумать?

Answer 1

[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.
Естественно, этот код ужасен. Не повторяйте в продакшене.

Comments

[Hello World]

это олимпиадное программирование. смысл писать какой-то красивый код? Тут важно отразить логику программы, а не архитектуру.

[SagePtr]

Hello World, в том, чтобы прививать себе привычку писать красивый код (если это не в сильно ущерб времени оказывается, конечно же).
Если бы вы не кидали всё в один цикл, а сначала проверяли одно, потом другое (в разных циклах) - то у вас не возникло бы той проблемы, из-за которой 13 тест проваливался, выиграли бы в данном случае время, и не заработали бы штрафное время (если бы это на реальном контесте происходило).
Так что красивый и структурированный код не только выглядит красиво, но и значительно снижает вероятность наделать ошибки.

Answer 2

[SagePtr]

Собственно, ошибка будет, если в графе встретится соответствие и этому условию:

if (i == j and G[i][j] == 1):

И этому условию:

elif (G[i][j] != G[j][i]):

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

Контртест:

0 1
0 1