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}

#include <bits/stdc++.h>



using namespace std;

ifstream cin("retea1.in");
ofstream cout("retea1.out");

stack <int> S;
int rezi[301] , u , ok;
int n , m , x , y , v[1001] , L[1001] , cnt , inS[1001] , rez , e , s[1001] , viz[1001] , a[301][301] , f[301];
vector <int> G[1001];
vector <int> P[1001];
vector <int>c;
vector <vector<int>> cc;

void tarjan(int nod)
{
    cnt++;
    v[nod] = L[nod] = cnt;
    S.push(nod);
    inS[nod] = 1;
    for(auto i:G[nod])
    {
        if(!v[i]) tarjan(i) , L[nod] = min(L[nod] , L[i]);
        else if(inS[i] == 1) L[nod] = min(L[nod] , v[i]);
    }
    if(v[nod] == L[nod])
    {
        c.clear();
        while(1)
        {
            int val = S.top();
            S.pop();
            c.push_back(val);
            inS[val] = 0;
            if(nod == val) break;
        }
        rez++;
        for(auto i:c)
            s[i] = rez;
    }
}

int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= n ; j++)
        {
            cin >> a[i][j];
            if(a[i][j] == 1)
                G[i].push_back(j);
        }
    for(int i = 1 ; i <= n ; i++)
        if(!v[i]) tarjan(i);

    for(int i = 1 ; i <= n ; i++)
        f[s[i]]++;

    for(int i = 1 ; i <= n ; i++)
    {
        if(f[i] > 1)
        {
            for(int j = 1 ; j <= n ; j++)
                if(i == s[j]) rezi[++u] = j;
        }
        else if(f[i] == 1)
        {
            for(int j = 1 ; j <= n ; j++)
                if(i == s[j] && a[j][j] == 1) rezi[++u] = j;
        }
    }
    sort(rezi + 1 , rezi + u + 1);
    cout << "{";
    for(int i = 1 ; i <= u ; i++)
    {
        if(ok == 0) cout << rezi[i] , ok++;
        else cout << "," << rezi[i];
    }
    cout << "}";


}