Rus Marius: 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?...

2024-01-06T21:10:54Z

Pagină nouă: = Cerința = Gigel are un graf cu <code>n</code> noduri și <code>m</code> 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 <code>a</code> și <code>b</code> este <code>a + b</code>, care este costul total minim al muchiilor care trebuie adăugate astfel încât graful să devină conex?...

New page

= Cerința =
Gigel are un graf cu <code>n</code> noduri și <code>m</code> 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 <code>a</code> și <code>b</code> este <code>a + b</code>, 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 <code>unireIN.txt</code> conține pe prima linie numerele <code>n</code> și <code>m</code>, pe a doua linie conține numărul <code>c</code>, reprezentând numărul cerinței <code>1 ≤ c ≤ 2</code>, iar pe următoarele <code>m</code> linii se află muchiile grafului <code>a b</code>, <code>1 ≤ a, b ≤ n</code>, <code>a ≠ b</code>.

= Date de ieșire =
Fișierul de ieșire <code>unireOUT.txt</code> va conține pe prima linie numărul <code>S</code>, 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 =

* <code>1 ≤ n ≤ 100000</code>, <code>0 ≤ m < n-1</code>
* Pentru teste în valoare de <code>30</code> de puncte, cerința va fi <code>1</code>.
* Pentru teste în valoare de <code>40</code> de puncte, <code>1 ≤ n ≤ 1000</code>.

= Exemplul 1: =
<code>unireIN.txt</code>
6 3
1
1 2
3 4
5 6
<code>unireOUT.txt</code>
2

= Exemplul 2: =
<code>unireIN.txt</code>
1000001 3
1
1 2
3 4
5 6
<code>unireOUT.txt</code>
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>

3364 - Unire - Revision history