Advertisement
Guest User

Untitled

a guest
Jan 28th, 2015
176
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.82 KB | None | 0 0
  1. n, m = list(map(int, input().split()))
  2. graph = [[] for i in range(n)]
  3. for i in range(m):
  4.     x, y = list(map(int, input().split()))
  5.     graph[x - 1].append(y - 1)
  6.     graph[y - 1].append(x - 1)
  7. color = [-1 for i in range(n)]
  8.  
  9. def dfs(x):
  10.     global graph, res_1
  11.     for i in range(len(graph[x])):
  12.         if color[graph[x][i]] == -1:
  13.             color[graph[x][i]] = (color[x] + 1) % 2
  14.             dfs(graph[x][i])
  15.         else:
  16.             if color[graph[x][i]] == color[x]:
  17.                 res_1 = False
  18.     return
  19.  
  20. res = True
  21. for i in range(n):
  22.     if color[i] == -1:
  23.         color[i] = 0
  24.         res_1 = True
  25.         dfs(i)
  26.         res = res and res_1
  27. if res:
  28.     print('YES')
  29.     for i in range(len(color)):
  30.         if color[i] == 0:
  31.             print(i + 1, end=' ')
  32.        
  33. else:
  34.     print('NO')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement