Advertisement
Guest User

Untitled

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