0592 - Kruskal

Cerința

Se dă un graf neorientat ponderat conex cu n vârfuri și m muchii – în care fiecare muchie are asociat un cost, număr natural strict pozitiv. Folosind algoritmul lui Kruskal, determinați un arbore parțial de cost minim.

Date de intrare

Fișierul de intrare kruskalIN.txt conține pe prima linie numerele n m, iar următoarele linii câte un triplet i j c, cu semnificația: există muchia (i j) și are costul c.

Date de ieșire

Fișierul de ieșire kruskalOUT.txt va conține pe prima linie costul arborelui de cost minim determinat, iar pe următoarele n-1 linii câte o pereche de numere i j, cu semnificația că muchia (i j) aparține arborelui parțial de cost minim determinat. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

• 1 ≤ n ≤ 100
• costul unei muchii va fi mai mic decât 1000

Exemplul 1:

kruskalIN.txt

7 11
1 2 2
1 7 4
2 3 3
2 5 2
2 6 3
2 7 3
3 4 1
3 5 2
4 5 1
5 6 3
6 7 5

kruskalOUT.txt

12
3 4
4 5
1 2
2 5
2 6
2 7

Exemplul 2:

kruskalIN.txt

101 11
1 2 2
1 7 4
2 3 3
2 5 2
2 6 3
2 7 3
3 4 1
3 5 2
4 5 1
5 6 3
6 7 5

kruskalOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python" line="1"> import sys

class Position:

   def __init__(self, i, j, c):
       self.i = i
       self.j = j
       self.c = c

def union(parent, a, b):

   parent[a] = parent[b]

def find(parent, a):

   if a == parent[a]:
       return a
   else:
       parent[a] = find(parent, parent[a])
       return parent[a]

def kruskal(n, m, graph, fout):

   parent = [i for i in range(n + 1)]
   result = 0
   cnt = 0
   A = []

   for edge in graph:
       r1 = find(parent, edge.i)
       r2 = find(parent, edge.j)
       if r1 != r2:
           result += edge.c
           A.append(edge)
           cnt += 1
           union(parent, r1, r2)

   fout.write(f"{result}\n")
   for edge in A:
       fout.write(f"{edge.i} {edge.j}\n")

def check_restrictions(n, m, graph):

   if not (1 <= n <= 100):
       return False
   for edge in graph:
       if not (edge.c < 1000):
           return False
   return True

def main():

   fin = open("kruskalIN.txt", "r")
   fout = open("kruskalOUT.txt", "w")

   n, m = map(int, fin.readline().split())

   graph = []
   for _ in range(m):
       x, y, w = map(int, fin.readline().split())
       graph.append(Position(x, y, w))

   graph.sort(key=lambda edge: edge.c)

   if not check_restrictions(n, m, graph):
       fout.write("Datele nu corespund restrictiilor impuse\n")
   else:
       kruskal(n, m, graph, fout)

   fin.close()
   fout.close()

if __name__ == "__main__":

   main()

</syntaxhighlight>