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

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Retea:

#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;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1707 Retea

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1707 Retea de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1707 Retea