Brianna Waltner: Pagină nouă: == Cerinţa == Se consideră o rețea formată din '''n''' servere, numerotate de la '''1''' la '''n'''. În rețea există m perechi de servere '''x y''' cunoscute între care există legături de comunicație directe. Între oricare două servere din rețea există legături, fie directe, fie prin intermediul altor servere. Stabiliți pentru fiecare dintre cele '''n''' servere dacă eliminarea sa din rețea conduce la pierderea legăturii dintre cel puțin două servere r...

2024-01-03T17:24:57Z

Pagină nouă: == Cerinţa == Se consideră o rețea formată din '''n''' servere, numerotate de la '''1''' la '''n'''. În rețea există m perechi de servere '''x y''' cunoscute între care există legături de comunicație directe. Între oricare două servere din rețea există legături, fie directe, fie prin intermediul altor servere. Stabiliți pentru fiecare dintre cele '''n''' servere dacă eliminarea sa din rețea conduce la pierderea legăturii dintre cel puțin două servere r...

New page

== Cerinţa ==
Se consideră o rețea formată din '''n''' servere, numerotate de la '''1''' la '''n'''. În rețea există m perechi de servere '''x y''' cunoscute între care există legături de comunicație directe. Între oricare două servere din rețea există legături, fie directe, fie prin intermediul altor servere.

Stabiliți pentru fiecare dintre cele '''n''' servere dacă eliminarea sa din rețea conduce la pierderea legăturii dintre cel puțin două servere rămase.
== Date de intrare ==
Fișierul de intrare '''reteain.txt''' conține pe prima linie numerele '''n''' si '''m'''. Pe următoarele '''m''' linii se vor afla câte două numere naturale '''x y''', reprezentând perechi de servere între care există legături directe.
== Date de ieșire ==
Fișierul de ieșire '''reteaout.txt''' va conține pe prima linie '''n''' numere naturale '''0''' sau '''1''':
* al '''i'''-lea număr va fi '''0''' dacă prin eliminarea serverului cu numărul i rămân legături între oricare două servere rămase
* al '''i'''-lea număr va fi '''1''' dacă prin eliminarea sa se pierde legătura între cel puțin două servere rămase.
== Restricţii şi precizări ==
* '''1 &les; n &les; 100'''
* '''1 &les; x,y &les; n'''
== Exemplul 1 ==
;'''reteain.txt'''
5 5
1 2
2 3
1 3
3 4
4 5
;'''reteaout.txt'''
Datele de intrare corespund restrictiilor impuse
0 0 1 1 0
== Exemplul 2 ==
;'''reteain.txt'''
101 1
1 2
;'''reteaout.txt'''
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
from collections import defaultdict

def dfs(v, visited, graph):
visited[v] = True
for u in graph[v]:
if not visited[u]:
dfs(u, visited, graph)

def main():
with open('reteain.txt', 'r') as fin:
n, m = map(int, fin.readline().split())
edges = [list(map(int, fin.readline().split())) for _ in range(m)]
if not (1 <= n <= 100) or not all(1 <= x <= n and 1 <= y <= n for x, y in edges):
print("Datele de intrare nu corespund restrictiilor impuse")
return
print("Datele de intrare corespund restrictiilor impuse")
graph = defaultdict(list)
for x, y in edges:
graph[x].append(y)
graph[y].append(x)
result = []
for i in range(1, n+1):
visited = [False] * (n+1)
visited[i] = True
dfs((i % n) + 1, visited, graph)
result.append('0' if all(visited[1:n+1]) else '1')
with open('reteaout.txt', 'w') as fout:
fout.write(' '.join(result))

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

== Explicaţie ==
Serverul '''1''' daca este eliminat nu întrerupe legătura deoarece exista lanțul de legături '''2 - 3 - 4 - 5''' pe care nu îl afectează.
Serverul '''2''' dacă este eliminat nu întrerupe legătura deoarece exista lanțul de legături '''1 - 3 - 4 - 5''' pe care nu îl afectează.
Serverul '''3''' dacă este eliminat, serverele '''1''' și '''2''' nu mai pot comunica cu serverele '''4''' și '''5'''.
Serverul '''4''' daca este eliminat, serverele '''1''', '''2''' și '''3''' nu mai pot comunica cu serverul '''5'''.
Serverul '''5''' dacă este eliminat nu întrerupe legătura deoarece serverele '''1''', '''2''', '''3''', '''4''' sunt legate intre ele.

1707 - Retea - Revision history