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

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()

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.