# PBinfo #1707 – Retea – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: andrei

## Enunț

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 retea.in 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 retea.out 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

Exemplu:
retea.in

5 5
1 2
2 3
1 3
3 4
4 5
retea.out

0 0 1 1 0
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.

## Cod sursă C++

```cpp
#include <fstream>
#include <cstring>
#include <list>
using namespace std;
ifstream fin("retea.in");
ofstream fout("retea.out");
int use[101],n,m,k,v[101][101],i,x,y;
list < int > G[101];
void DF( int nod, int srv )
{
    ++k;
    use[ nod ] = 1;
    for( auto it : G[ nod ] )
        if( !use[ it ] && it != srv )
            DF( it , srv );
}
int main()
{
    fin>>n>>m;
    for( i = 1 ; i <= m ; i++ )
    {
        fin>>x>>y;
        G[ x ].push_back( y );
        G[ y ].push_back( x );
    }
    for( i = 1 ; i <= n ; i++ )
    {
        k = 0;
        memset( use , 0 , sizeof( use ) );
        if( i == 1 )
        {
            DF( 2 , 1 );
            if( k == n- 1 )
                fout<<0<<' ';
            else
                fout<<1<<' ';
        }
        else
        {
            DF( 1 , i );
            if( k == n- 1 )
                fout<<0<<' ';
            else
                fout<<1<<' ';
        }
    }
return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1707)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1707/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1707/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)