FilesExpand file tree

 main

/

Road_Reparation.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

51 lines (36 loc) · 1.14 KB

 main

/

Road_Reparation.py

Copy path

Top

File metadata and controls

• Code
• Blame

51 lines (36 loc) · 1.14 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

####################################################################################

# Please consider trying a few more times before referring to this code.

# Code might be incorrect - TLE / Wrong Answer (especially filenames with _1 , _2)

# Pedagogical > Pythonic

####################################################################################

I = lambda : map(int, input().split())

n, m = I()

edges = []

for _ in range(m):

a, b, w = I()

edges.append((a, b, w))

edges = sorted(edges, key = lambda x: x[2])

# kruskal - union find structure

link = [i for i in range(n + 1)]

size = [1 for i in range(n + 1)]

def find(x):

while True:

if link[x] == x: break

else: x = link[x]

return x

final_wt = 0

edge_cnt = 0

for (a, b, w) in edges:

rep_a = find(a)

rep_b = find(b)

if rep_a == rep_b: continue

if size[rep_a] > size[rep_b]:

rep_a, rep_b = rep_b, rep_a # swap

link[rep_a] = rep_b

size[rep_b] += size[rep_a]

final_wt += w

edge_cnt += 1

if edge_cnt == n - 1: # tree

print(final_wt)

else: print("IMPOSSIBLE")

# I once again ask you to try a few more times before referring here