-
Notifications
You must be signed in to change notification settings - Fork 0
/
20040.py
54 lines (40 loc) · 1.11 KB
/
20040.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import sys
class DSet():
class Node:
def __init__(self, key):
self.parent = self
self.rank = 0
def __init__(self, keys):
self.nodes = {}
for key in keys:
self.nodes[key] = self.Node(key)
def create(self, key):
if key not in self.nodes:
self.nodes[key] = self.Node(key)
def find(self, key):
node = self.nodes[key]
while node.parent != node:
node, node.parent = node.parent, node.parent.parent
return node
def union(self, a, b):
x = self.find(a)
y = self.find(b)
if x != y:
# Union by rank
if x.rank < y.rank:
x, y = y, x
y.parent = x
if x.rank == y.rank:
x.rank += 1
n, m = map(int, sys.stdin.readline().strip().split())
dots = DSet(list(range(n)))
sol = 0
for i in range(m):
a, b = map(int, sys.stdin.readline().strip().split())
if sol > 0:
continue
elif sol == 0 and dots.find(a) == dots.find(b):
sol = i+1
else:
dots.union(a, b)
print(sol)