Editing 0592 - Kruskal

= Cerința =
Se dă un graf neorientat ponderat conex cu <code>n</code> vârfuri și <code>m</code> 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 <code>kruskalIN.txt</code> conține pe prima linie numerele <code>n m</code>, iar următoarele linii câte un triplet <code>i j c</code>, cu semnificația: există muchia <code>(i j)</code> și are costul <code>c</code>.

= Date de ieșire =
Fișierul de ieșire <code>kruskalOUT.txt</code> va conține pe prima linie costul arborelui de cost minim determinat, iar pe următoarele <code>n-1</code> linii câte o pereche de numere <code>i j</code>, cu semnificația că muchia <code>(i j)</code> 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 =

* <code>1 ≤ n ≤ 100</code>
* costul unei muchii va fi mai mic decât <code>1000</code>

= Exemplul 1: =
<code>kruskalIN.txt</code>
 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
<code>kruskalOUT.txt</code>
 12
 3 4
 4 5
 1 2
 2 5
 2 6
 2 7

== Exemplul 2: ==
<code>kruskalIN.txt</code>
 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
<code>kruskalOUT.txt</code>
 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>