(E_and_n)
| 260 | |
| 261 | |
| 262 | def krusk(E_and_n): |
| 263 | # Sort edges on the basis of distance |
| 264 | (E, n) = E_and_n |
| 265 | E.sort(reverse=True, key=lambda x: x[2]) |
| 266 | s = [set([i]) for i in range(1, n + 1)] |
| 267 | while True: |
| 268 | if len(s) == 1: |
| 269 | break |
| 270 | print(s) |
| 271 | x = E.pop() |
| 272 | for i in xrange(len(s)): |
| 273 | if x[0] in s[i]: |
| 274 | break |
| 275 | for j in xrange(len(s)): |
| 276 | if x[1] in s[j]: |
| 277 | if i == j: |
| 278 | break |
| 279 | s[j].update(s[i]) |
| 280 | s.pop(i) |
| 281 | break |
| 282 | |
| 283 | |
| 284 | # find the isolated node in the graph |