Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- edges = []
- vertices = []
- def DFS(vertex: tuple):
- vertex[1] = True
- for edge in edges:
- if edge[0] == vertex[0]:
- v = vertices[edge[1] - 1]
- if not v[1]:
- DFS(v)
- if edge[1] == vertex[0]:
- v = vertices[edge[0] - 1]
- if not v[1]:
- DFS(v)
- def main():
- verts = set()
- f = open('friends.in')
- f.readline() # skipping first line
- for line in f:
- edge = list(map(int, line.split()))
- edges.append(edge)
- verts.add(edge[0])
- verts.add(edge[1])
- for vertex in verts:
- vertices.append([vertex, False])
- k = 0
- nodes = []
- for vertex in vertices:
- if not vertex[1]:
- DFS(vertex)
- nodes.append(vertex[0])
- k += 1
- print(k - 1)
- if not k == 1:
- for i, node in enumerate(nodes[:-1]):
- print('%d %d' % (nodes[i], nodes[i + 1]))
- main()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement