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

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()

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.