Oros Ioana Diana: Pagină nouă: = 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...

2024-05-18T19:55:47Z

Pagină nouă: = 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...

New page

= 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>

0592 - Kruskal - Revision history