3364 - Unire

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.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

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

2

Exemplul 2:

unireIN.txt

1000001 3
1
1 2
3 4
5 6

unireOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def check_restrictions(n, m):

   return not (1 <= n <= 100000 and 0 <= m < n - 1)

def dfs(v, c, C, G):

   C[v] = c
   for i in G[v]:
       if not C[i]:
           dfs(i, c, C, G)

def main():

   with open("unireIN.txt", "r") as input_file, open("unireOUT.txt", "w") as output_file:
       n, m = map(int, input_file.readline().split())

       if check_restrictions(n, m):
           output_file.write("Datele nu corespund restrictiilor impuse\n")
           return

       c = int(input_file.readline().strip())

       G = [[] for _ in range(100001)]
       C = [0] * 100001
       nc = 0
       f = [0] * 100001
       s = 0

       for _ in range(m):
           x, y = map(int, input_file.readline().split())
           G[x].append(y)
           G[y].append(x)

       for i in range(1, n + 1):
           if not C[i]:
               nc += 1
               dfs(i, i, C, G)

       if c == 1:
           output_file.write(str(nc - 1) + "\n")
       else:
           C.sort()
           for i in range(2, n + 1):
               if C[1] != C[i] and f[C[i]] == 0:
                   s += (C[1] + C[i])
               f[C[i]] += 1

           output_file.write(str(s) + "\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>