serega1112

Is graph a tree

Mar 6th, 2021
131
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.78 KB | None | 0 0
  1. n = int(input())
  2.  
  3. adj = []
  4. while n:
  5.     adj.append(list(map(int, input().split())))
  6.     n -= 1
  7.  
  8. visited = [0] * len(adj)
  9. res = 'YES'
  10. count = 0
  11. for i in range(len(adj)):
  12.     if not visited[i]:
  13.         count += 1
  14.         if count > 1:
  15.             res = 'NO'
  16.             break
  17.         st = [(i, None)]
  18.         visited[i] = 1
  19.         while st:
  20.             cur, parent = st.pop()
  21.             for j in range(len(adj[cur])):
  22.                 if adj[cur][j]:
  23.                     if not visited[j]:
  24.                         st.append((j, cur))
  25.                         visited[j] = 1
  26.                     elif j != parent:
  27.                         res = 'NO'
  28.                         break
  29.             if res == 'NO':
  30.                 break
  31.     if res == 'NO':
  32.         break
  33.  
  34. print(res)
Advertisement
Add Comment
Please, Sign In to add comment