Question

HELLO! Am si eu nevoie de ajutor la doua probleme de pe pbingo repede.
VA ROG CAT MAI URGENT CA SUNT PENTRU MAINE LA 12:00
1)Problema cu codul 963 suna asa
La ştrandul Junior din oraşul nostru s-au construit n bazine pentru înot. Fiecare bazin a fost dotat cu câte un robinet pentru umplerea acestuia cu apă. Între m perechi distincte de bazine, a fost instalată câte o ţeavă prin care apa din cele două bazine din fiecare pereche să poată circula. Astfel, cele două bazine din pereche pot fi umplute prin deschiderea unui singur robinet.

Administratorul bazei a numerotat bazinele cu numerele distincte de la 1 la n şi a notat în registrul lui cele m perechi de numere (x1,y1), (x2,y2),…., (xm,ym) corespunzând perechilor de bazine între care a fost instalată câte o ţeavă. Pentru a umple toate bazinele cu apă, administratorul doreşte să deschidă un număr minim de robinete.

Cerinţă.

Scrieţi un program care să citească numerele naturale n şi m, şi cele 2*m numere naturale x1, y1, x2, y2,…., xm, ym, cu semnificația din enunț, şi care să afişeze cel mai mic număr k de robinete pe care trebuie să le deschidă administratorul astfel încât să fie umplute cu apă toate bazinele.

Date de intrare
Fișierul de intrare bazine.in conține pe prima linie numerele n m, iar pe următoarele m linii căte o pereche de numere x y.

Date de ieșire
Fișierul de ieșire bazine.out va conține pe prima linie numărul k determinat.

Restricții și precizări
10 ≤ n ≤ 100
8 ≤ m ≤ 400
nu există două perechi de numere (x,y), (x’,y’) astfel încât x=x’ şi y=y’ sau x=y’ şi y=x’ printre cele m perechi citite din fişier
1 ≤ xi ≤ n , 1 ≤ yi ≤ n , xi ≠ yi
fiecare bazin poate fi cuplat la unul sau mai multe bazine prin câte o ţeavă, sau la nici un bazin



Exemplu
bazine.in

10 8
1 6
4 5
8 6
3 7
9 4
1 8
10 6
1 10
bazine.out

4
Explicație
Apa din bazinele 1, 6, 8 şi 10 comunică doar între acestea, fiind instalate ţevi. Astfel pentru aceste patru bazine este necesar să se deschidă un singur robinet pentru umplerea lor.

Apa din bazinele 4, 5 şi 9 comunică, deoarece între acestea sunt ţevi. Astfel pentru aceste bazine este necesar să se deschidă un singur robinet.

Pentru bazinele 3 şi 7 între care există teavă, se deschide un singur robinet, cele două bazine nefiind legate prin ţevi de celelalte bazine

Bazinul 2 nu este cuplat cu niciun alt bazin, fiind necesar să se deschidă robinetul acestuia.

În total se deschid doar 4 robinete pentru a alimenta toate bazinele

2) Problema cu codul 1707 suna asa:
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.

Answer 1

Răspuns:

ambele probleme folosesc algoritmul lui Depth-first search (Prima Cautare in Adancime)

#include<bits/stdc++.h>

using namespace std;

ifstream in("bazine.in");

ofstream out("bazine.out");

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

inline void dfs(int r,int nrc)

{

   v[r]=nrc;

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

       if(!v[i] && (a[r][i] || a[i][r]))

           dfs(i,nrc);

}

inline void citire()

{

   in>>n>>m;

   while(in>>x>>y)

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

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

       if(!v[i])

           dfs(i,++nrc);

   out<<nrc;

}

int main()

{

   citire();

   return 0;

}

Explicație:

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

}