Question

VA ROG!!
problema #1707 retea pbinfo
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

Answer 1

Răspuns:

#include<bits/stdc++.h>

using namespace std;

ifstream in("retea.in");

ofstream out("retea.out");

int a[101][101],n,m,x,y;

inline void dfs(int x,int nrc,int v[],int y)

{

   v[x]=nrc;

   for(int i=1;i<=n;i++)

       if(!v[i] && a[x][i] && x!=y && i!=y)

           dfs(i,nrc,v,y);

}

inline void verif(int x)

{

   register int v[101],nrc=0;

   memset(v,0,sizeof(v));

   for(int i=1;i<=n;i++)

       if(!v[i] && i!=x)

           dfs(i,++nrc,v,x);

   nrc==1?out<<0<<" ":out<<1<<" ";

}

inline void citire()

{

   in>>n>>m;

   while(in>>x>>y)

       a[x][y]=a[y][x]=1;

   for(int i=1;i<=n;i++)

       verif(i);

}

int main()

{

   citire();

   return 0;

}

Explicație: