Simina: Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu `n` noduri și `m` muchii și un șir de `q` noduri. Să se determine pentru fiecare nod `x` din șir numărul de noduri din componenta conexă din care face parte `x`. = Date de intrare = Fişierul de intrare `componenteconexe5IN.txt` conține pe prima linie numerele `n m`, reprezentând numărul de noduri și numărul de muchii ale graful...

2023-12-13T12:33:48Z

Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu <code>n</code> noduri și <code>m</code> muchii și un șir de <code>q</code> noduri. Să se determine pentru fiecare nod <code>x</code> din șir numărul de noduri din componenta conexă din care face parte <code>x</code>. = Date de intrare = Fişierul de intrare <code>componenteconexe5IN.txt</code> conține pe prima linie numerele <code>n m</code>, reprezentând numărul de noduri și numărul de muchii ale graful...

New page

= Cerinţa =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> noduri și <code>m</code> muchii și un șir de <code>q</code> noduri. Să se determine pentru fiecare nod <code>x</code> din șir numărul de noduri din componenta conexă din care face parte <code>x</code>.

= Date de intrare =
Fişierul de intrare <code>componenteconexe5IN.txt</code> conține pe prima linie numerele <code>n m</code>, reprezentând numărul de noduri și numărul de muchii ale grafului. Fiecare dintre următoarele <code>m</code> 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>.

Următoarea linie conține numărul <code>q</code>, iar ultima linie a fișierului de intrare conține un șir de <code>q</code> noduri, seprate prin câte un spațiu.

= Date de ieşire =
Fişierul de ieşire <code>componenteconexe5OUT.txt</code> va conține <code>q</code> linii; fiecare linie va conține numărul de noduri din componenta conexă a nodului corespunzător din șir.

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 1000</code>
* <code>1 ≤ i , j ≤ n</code>
* <code>1 ≤ q ≤ 1000</code>
* <code>1 ≤ x ≤ n</code>

= Exemplul 1 =
<code>componenteconexe5IN.txt</code>
5 3
1 2
3 5
2 4
3
2 5 1
<code>componenteconexe5OUT.txt</code>
3
2
3

= Exemplul 2 =
<code>componenteconexe5IN.txt</code>
1001 1001
<code>componenteconexe5OUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificare_restrictii(n, m, q, noduri_interes):
if not (1 <= n <= 1000 and 1 <= m <= n * (n - 1) // 2 and 1 <= q <= 1000):
return False
for nod in noduri_interes:
if not (1 <= nod <= n):
return False
return True

def dfs(nod, graf, vizitat, componenta):
vizitat[nod] = True
componenta.append(nod)
for vecin in graf[nod]:
if not vizitat[vecin]:
dfs(vecin, graf, vizitat, componenta)

def gaseste_componente_conexe(graf, noduri_interes):
componente = []
vizitat = {nod: False for nod in graf}
for nod in noduri_interes:
if not vizitat[nod]:
componenta = []
dfs(nod, graf, vizitat, componenta)
componente.append(componenta)
return componente

def main():
# Citirea datelor de intrare
with open("componenteconexe5IN.txt", "r") as fisier:
try:
n, m = map(int, fisier.readline().split())
graf = {i: [] for i in range(1, n + 1)}
for _ in range(m):
muchie = list(map(int, fisier.readline().split()))
if len(muchie) != 2 or not (1 <= muchie[0] <= n and 1 <= muchie[1] <= n):
raise ValueError("Datele nu corespund formatului asteptat.")
graf[muchie[0]].append(muchie[1])
graf[muchie[1]].append(muchie[0])
q = int(fisier.readline())
noduri_interes = list(map(int, fisier.readline().split()))
except ValueError as e:
with open("componenteconexe5OUT.txt", "w") as fisier_out:
fisier_out.write(str(e))
return

# Verificarea restricțiilor
if not verificare_restrictii(n, m, q, noduri_interes):
with open("componenteconexe5OUT.txt", "w") as fisier_out:
fisier_out.write("Datele nu corespund restrictiilor impuse")
return

# Identificarea componentelor conexe
componente = gaseste_componente_conexe(graf, set(noduri_interes))

# Scrierea rezultatelor în fișierul de ieșire
with open("componenteconexe5OUT.txt", "w") as fisier_out:
for nod in noduri_interes:
for componenta in componente:
if nod in componenta:
fisier_out.write(str(len(componenta)) + "\n")
break

if __name__ == "__main__":
main()
</syntaxhighlight>

4073 - Componente Conexe 5 - Revision history