1707 - Retea

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 ⩽ n ⩽ 100
• 1 ⩽ x,y ⩽ 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.