Brianna Waltner: Pagină nouă: == Cerinţa == Gigel are un graf cu '''n''' noduri și '''m''' muchii, care nu este conex. El dorește să afle răspunsul la două întrebări: 1) Care este numărul minim de muchii ce trebuie ađugate astfel încât graful să devină conex? 2) Dacă costul adăugării unei muchii între nodurile '''a''' și b este '''a + b''', care este costul total minim al muchiilor care trebuie adăugate astfel încât graful să devină conex? == Date de intrare == Fișierul de intra...

2024-01-03T23:39:33Z

Pagină nouă: == Cerinţa == Gigel are un graf cu '''n''' noduri și '''m''' muchii, care nu este conex. El dorește să afle răspunsul la două întrebări: 1) Care este numărul minim de muchii ce trebuie ađugate astfel încât graful să devină conex? 2) Dacă costul adăugării unei muchii între nodurile '''a''' și b este '''a + b''', care este costul total minim al muchiilor care trebuie adăugate astfel încât graful să devină conex? == Date de intrare == Fișierul de intra...

New page

== Cerinţa ==
Gigel are un graf cu '''n''' noduri și '''m''' muchii, care nu este conex. El dorește să afle răspunsul la două întrebări:

1) Care este numărul minim de muchii ce trebuie ađugate astfel încât graful să devină conex?

2) Dacă costul adăugării unei muchii între nodurile '''a''' și b este '''a + b''', care este costul total minim al muchiilor care trebuie adăugate astfel încât graful să devină conex?
== Date de intrare ==
Fișierul de intrare '''unirein.txt''' conține pe prima linie numerele '''n''' și '''m''', pe a doua linie conține numărul '''c''', reprezentând numărul cerinței '''1 &les; c &les; 2''', iar pe următoarele '''m''' linii se află muchiile grafului '''a b''', '''1 &les; a, b &les; n''', '''a ≠ b'''.
== Date de ieșire ==
Fișierul de ieșire '''unireout.txt''' va conține pe prima linie numărul '''S''', reprezentând răspunsul cerut de Gigel.
== Restricţii şi precizări ==
* '''1 &les; n &les; 100000, 0 &les; m &les; n-1'''
* Pentru teste în valoare de '''30''' de puncte, cerința va fi '''1'''.
* Pentru teste în valoare de '''40''' de puncte, '''1 &les; n &les; 1000'''.
== Exemplul 1 ==
;'''unirein.txt'''
6 3
1
1 2
3 4
5 6
;'''unireout.txt'''
Datele de intrare corespund restrictiilor impuse
2
== Exemplul 2 ==
;'''unirein.txt'''
100001 1
1
1 2
;'''unireout.txt'''
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
import heapq

def find(parent, i):
if parent[i] == i:
return i
return find(parent, parent[i])

def union(parent, rank, x, y):
xroot = find(parent, x)
yroot = find(parent, y)

if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1

def solve(n, c, edges):
parent = [i for i in range(n+1)]
rank = [0] * (n+1)

for a, b in edges:
union(parent, rank, a, b)

sets = [find(parent, i) for i in range(1, n+1)]
unique_sets = list(set(sets))

if c == 1:
return len(unique_sets) - 1
else:
costs = [i for i in unique_sets]
heapq.heapify(costs)
total_cost = 0

while len(costs) > 1:
cost1 = heapq.heappop(costs)
cost2 = heapq.heappop(costs)
total_cost += cost1 + cost2
heapq.heappush(costs, cost1 + cost2)

return total_cost

def main():
with open('unirein.txt', 'r') as f:
n, _ = map(int, f.readline().split())
c = int(f.readline())
edges = [list(map(int, line.split())) for line in f]

if not (1 <= n <= 100000):
print("Datele de intrare nu corespund restrictiilor impuse")
return

result = solve(n, c, edges)

with open('unireout.txt', 'w') as f:
f.write(str(result))

print("Datele de intrare corespund restrictiilor impuse")

if __name__ == "__main__":
main()
</syntaxhighlight>

== Explicaţie ==
Se vor uni nodurile '''1''' și '''3''', respectiv nodurile '''1'''și '''5''', s-au folosit '''2''' muchii, iar costul total va fi '''1 + 3 + 1 + 5 = 10'''.

4290 - Gaseste Ciclu - Revision history