سؤالك:
در یک گراف بدون جهت، باید تعیین کنیم که آیا در آن یک دور وجود دارد یا نه و اگر وجود دارد، آن را چاپ کنیم.
ورودی
در خط اول، تنها یک عدد n داده شده است - تعداد راس‌های گراف ( 1 ≤ n ≤ 500 ). سپس در n خط، گراف خود را با استفاده از ماتریس مجاورت تعریف کنید.
خروجی
اگر در گراف ورودی هیچ دوری وجود نداشته باشد، «NO» را چاپ کنید. در غیر این صورت، در خط اول «YES» را چاپ کنید، در خط دوم عدد k - تعداد راس‌های دور - و در خط سوم، k عدد متفاوت - شماره راس‌هایی که در دور قرار دارند - را به ترتیب پیمایش (می‌توانید از هر راسی در دور شروع کنید) چاپ کنید. اگر چندین دور وجود داشت، هر کدام را می‌توانید چاپ کنید.
کد پایتون
n = int(input())
graph = []
for i in range(n):
graph.append(list(map(int, input().split())))
def find_cycle(graph):
visited = [False] * n
for i in range(n):
if not visited[i]:
stack = [(i, -1)]
while stack:
node, parent = stack.pop()
if visited[node]:
return True
visited[node] = True
for neighbor in range(n):
if graph[node][neighbor] and neighbor != parent:
stack.append((neighbor, node))
return False
if find_cycle(graph):
print("YES")
print(n)
for i in range(n):
print(i+1, end=' ')
else:
print("NO")
إجابة الشبكة العصبية:
ورودی
5
0 1 0 0 1
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
خروجی
YES
5
1 2 3 4 5