Simina: Pagină nouă: = Cerinţa = Se dă un graf neorientat cu `n` vârfuri. Determinați numărul maxim de vârfuri dintr-o componentă conexă și numărul de componente conexe care au acest număr maxim de vârfuri. = Date de intrare = Fişierul de intrare `ccmaxIN.txt` conţine pe prima linie numărul `n`, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o pereche de numere `i j`, cu semnificația c...

2023-12-13T12:40:29Z

Pagină nouă: = Cerinţa = Se dă un graf neorientat cu <code>n</code> vârfuri. Determinați numărul maxim de vârfuri dintr-o componentă conexă și numărul de componente conexe care au acest număr maxim de vârfuri. = Date de intrare = Fişierul de intrare <code>ccmaxIN.txt</code> conţine pe prima linie numărul <code>n</code>, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o pereche de numere <code>i j</code>, cu semnificația c...

New page

= Cerinţa =
Se dă un graf neorientat cu <code>n</code> vârfuri. Determinați numărul maxim de vârfuri dintr-o componentă conexă și numărul de componente conexe care au acest număr maxim de vârfuri.

= Date de intrare =
Fişierul de intrare <code>ccmaxIN.txt</code> conţine pe prima linie numărul <code>n</code>, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o pereche de numere <code>i j</code>, cu semnificația că există muchie între <code>i</code> și <code>j</code>.

= Date de ieşire =
Fişierul de ieşire <code>ccmaxOUT.txt</code> va conţine pe prima linie numărul maxim de vârfuri dintr-o componentă conexă și numărul de componente conexe care au acest numar maxim de vârfuri, separate prin exact un spațiu.

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 100</code>
* <code>1 ≤ i , j ≤ n</code>
* în fișierul de intrare muchiile se pot repeta

= Exemplul 1 =
<code>ccmaxIN.txt</code>
7
1 5
3 5
2 4
6 4
<code>ccmaxOUT.txt</code>
3 2

= Explicație: =
Graful conține două componente cu număr maxim de vârfuri, fiecare având câte 3 vârfuri. Acestea sunt {1,3,5} și {2,4,6}, iar vârful 7 este izolat.

== Exemplul 2 ==
<code>ccmaxIN.txt</code>
101
<code>ccmaxOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def parcurgere_dfs(nod, vizitat, graf):
vizitat[nod] = True
dimensiune = 1
for vecin in graf[nod]:
if not vizitat[vecin]:
dimensiune += parcurgere_dfs(vecin, vizitat, graf)
return dimensiune

def verificare_restrictii(n, muchii):
if not (1 <= n <= 100):
return False
for i, j in muchii:
if not (1 <= i <= n) or not (1 <= j <= n):
return False
return True

def main():
with open("ccmaxIN.txt", "r") as infile:
n = int(infile.readline().strip())
muchii = [tuple(map(int, linie.split())) for linie in infile]

if not verificare_restrictii(n, muchii):
with open("ccmaxOUT.txt", "w") as outfile:
outfile.write("Datele nu corespund restrictiilor impuse\n")
return

graf = {i: [] for i in range(1, n + 1)}
for i, j in muchii:
graf[i].append(j)
graf[j].append(i)

dim_maxima = 0
numar_dim_maxima = 0
vizitat = [False] * (n + 1)

for nod in range(1, n + 1):
if not vizitat[nod]:
dimensiune_componenta = parcurgere_dfs(nod, vizitat, graf)
if dimensiune_componenta > dim_maxima:
dim_maxima = dimensiune_componenta
numar_dim_maxima = 1
elif dimensiune_componenta == dim_maxima:
numar_dim_maxima += 1

with open("ccmaxOUT.txt", "w") as outfile:
if dim_maxima == 0:
outfile.write("Datele nu corespund restrictiilor impuse\n")
else:
outfile.write(f"{dim_maxima} {numar_dim_maxima}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

4067 - CcMax - Revision history