Advertisement
Guest User

Untitled

a guest
Dec 1st, 2015
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.85 KB | None | 0 0
  1. # -*- coding: utf8 -*-
  2.  
  3. st=input().split()
  4. n=int(st[0])
  5. s=int(st[1])
  6. graf = [[0]  for i in range(n+1)]
  7. for i in range (s):
  8.     stroka=[int(x)for x in input().split()]
  9.     graf[stroka[0]].append(stroka[1])
  10.     graf[stroka[1]].append(stroka[0])     #создала матрицу смежности
  11.  
  12. visited=[False]*(n+1)                         #отмечаю посещенные вершины
  13. k=0
  14. q=[]
  15. def dfs(v):
  16.     visited[v]=True
  17.     if v!=0:
  18.         q.append(v)   #составляю список из посещенных вершин
  19.  
  20.     for w in graf[v]:
  21.         if visited[w]==False:
  22.             dfs(w)
  23.  
  24.  
  25. aaa=[0]
  26. for v in range(1,n+1):
  27.     if not visited[v]:
  28.         dfs(v)
  29.         k=k+1
  30.         q.sort()
  31.         aaa.append(q)
  32.         q=[]
  33. print(k)
  34. for i in aaa:
  35.     if i!=0:
  36.         print(len(i))
  37.         print(*i)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement