4067 - CcMax
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ă există muchie între i
și j
.
Date de ieşire
Fişierul de ieşire ccmaxOUT.txt
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
1 ≤ n ≤ 100
1 ≤ i , j ≤ n
- în fișierul de intrare muchiile se pot repeta
Exemplul 1
ccmaxIN.txt
7 1 5 3 5 2 4 6 4
ccmaxOUT.txt
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
ccmaxIN.txt
101
ccmaxOUT.txt
Datele nu corespund restrictiilor impuse
Rezolvare
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()