4290 - Gaseste Ciclu

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 ⩽ c ⩽ 2, iar pe următoarele m linii se află muchiile grafului a b, 1 ⩽ a, b ⩽ 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 ⩽ n ⩽ 100000, 0 ⩽ m ⩽ n-1
• Pentru teste în valoare de 30 de puncte, cerința va fi 1.
• Pentru teste în valoare de 40 de puncte, 1 ⩽ n ⩽ 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.