Pentru a testa o nouă topologie s-a construit o reţea de calculatoare în care fiecare calculator transmite informaţia unidirecţional către un singur calculator din reţea. Numim conexiune o pereche ordonată de calculatoare, nu neapărat distincte, în care primul este cel care trimite informaţia iar al doilea este cel care o recepţioneaza direct. Fiind dată o astfel de reţea şi conexiunile existente între calculatoarele care o alcătuiesc, să se determine submulţimea cu număr maxim de calculatoare-feed-back. Un calculator-feed-back are proprietatea că informația ce pleacă de la acesta ajunge, prin intermediul conexiunilor succesive, înapoi la calculatorul de la care a plecat.
Cerința
Scrieţi un program care, pentru o reţea cu n calculatoare numerotate de la 1 la n şi conexiuni precizate, determină submulţimea cu număr maxim de calculatoare-feed-back.
Date de intrare
Pe prima linie a fişierului de intrare retea1.in se află un număr natural nenul n, reprezentând numărul de calculatoare din reţea, iar pe fiecare dinre următoarele n linii, separate prin câte un spaţiu, câte n-1 valori 0 şi o valoare 1, cu semnificaţia: pe linia i, elementul de pe poziţia j este 1 dacă şi numai dacă există conexine între calculatorul i şi calculatorul j.
Date de ieșire
În fişierul de ieşire retea1.out se vor scrie pe prima linie calculatoarele-feed-back din submulţimea determinată. Elementele submulţimii sunt scrise în ordine crescătoare, separate prin câte o virgulă, fără spaţii iar submulţimea începe cu caracterul { şi se termină cu caracterul }. În fişierul de ieşire nu se vor scrie spaţii înainte, între sau după elementele mulţimii.
Restricții și precizări
1 ≤ n ≤ 300- un calculator poate să aibă o conexiune cu el însuşi
- un calculator poate avea o conexiune doar cu singur calculator
Exemplul 1:
retea1.in
5 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1
retea1.out
{1,2,4,5}
Explicație
Calculatorul 1 are conexiune cu calculatorul 4, calculatorul 4 are conexiune cu calculatorul 2, iar calculatorul 2 are conexiune cu calculatorul 1, deci oricare dintre calculatoarele 1, 2 sau 4 este calculator-feed-back. Calculatorul 5 are conexiune cu el însuşi deci este calculator-feed-back. Submulţimea finală este {1,2,4,5}.
Exemplul 2:
retea1.in
6 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0
retea1.out
{4,5} 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 retea1:
#include <bits/stdc++.h>
using namespace std;
ifstream f("retea1.in");
ofstream g("retea1.out");
int A[15001], n;
char c[15001], V[15001];
int main()
{
int x, i, j;
f >> n;
f.get();
for(i = 1; i <= n; i++)
{
V[i] = 0;
f.get(c, 15001);
f.get();
for(j = 0; j < n; j++)
if(c[2 * j] == '1') A[i] = j + 1;
}
for(i = 1; i <= n; i++)
if(V[i] == 0)
{
x = i;
for(j = 1; j <= n; j++)
if(V[j] == 1) V[j] = 0;
while(V[x] != 2)
{
V[x]++;
x = A[x];
}
}
for(i = 1, x = 0; i <= n; i++)
if(V[i] == 2) x++;
g << "{";
for(i = 1; i <= n; i++)
if (V[i] == 2)
{
if (--x > 0) g << i << ",";
else g << i;
}
g << '}';
g.close();
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 
.
Rezolvarea problemei #2232 retea1
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2232 retea1 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!