/*
Fie G(X,U)/*
Fie G(X,U)  graf neorientat reprezentat prin matrice de adiacenta
X multimea nodurilor , |X|=n , i.e. sujnt in total n noduri
U multimea arcelor , multime de perechi neordonate din X (i,j) cu i!=j

Fie x1 nod de start .
Se cere sa se efectueze o parcurgere a grafului pornind din nodul x1
navingand pe muchiile acestuia

exemplu  ( peters graph )


              * 1
            /   \
           2 *--*5
            |    |
           3 *--*4

fie x1=1 nod de start

Strategii de parcurgere

[I] DFS ( deep first search )

Consta in a vizita continuu prim adiacent nevizitat inca al curentului
( daca acesta exista )
pentru x1=1

              * 1
            /   \
           2 *--*5
            |    |
           3 *--*4

DFS(1)=1,2,3,4,5

ATT : strategia DFS este de tip BKTR  !~~

adica daca pentru nod curent nu exista ceea ce caut ( "prim adiacent nevizitat inca" )
ma intorc la nod anterior pentru a incerca explorare printr-un alt nod

Adica  pentru o variatie :



            * 1
            /   \
           2 *--*5
            |    |
           3 *--*4
          /
        6*

DFS(1)=1,2,3,4,5,6

Deci DFS fiind de tip BKTR exista abordari iterative ( in cicluri de tip while
" atata timp cat mai sunt succesori " i.e. "atata timp cat mai sunt tentative
de explorare din nod curent" ) sau recursive ( autoapel pentru
toti adiacentii nevizitati inca i.e. ciclul iterativ de tip while se transforma
in autoapel

Cu scopul unor optimziari exista formulari "degenerate" de BKTR
pentru a rula DFS



*/


#include<fstream>
#include<iostream>
using namespace std;

int n; // n=|X|
int G[100][100]; // G(X,U)
int S[100];         // solutia ( lista nodurilor vizitate )
int V[100];         // vector caracteristic al vizitatilor
int vf;
int top;


int read_data()
{ fstream  f;
   f.open("input.dat",ios::in);
   f>>n;
   for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)  f>>G[i][j];
  f>>vf;
/*
             * 1
            /   \
           2 *--*5
            |    |
           3 *--*4

vf=1

input.dat :

5
0 1 0 0 1
1 0 1 0 1
0 1 0 1 0
0 0 1 0 1
1 1 0 1 0
1
*/

}
/*
int DFS_IT(int vf)
{
top=1;
S[top]=vf
cout<<vf;
V[vf]=1;
int gasit=1;
while (gasit) {
            gasit=0;
             for(int i=1;i<=n;i++)
                {  if () { gasit=1;
                                                                  break;
                                                                }
                }
            if (gasit==1)  { top++;
                                  S[top]=i;
                                  V[i]=1;
                                  cout<<i<<" ";
                                }
                     else top--;
                }
}
*/

int succ(int S[100],int top)
{
if (S[top]<n)  {
                        S[top]++;
                        V[top] = 1;
                        return 1;
                    }
return 0;
}

int valid(int S[100],int top)
{
if (top==1) return 1;
for(int i=1;i<top;i++)
   if (S[i]==S[top])  {return 0;}
return 1;
}

int tipar(int S[100],int top)
{
cout<<endl;
for(int i=1;i<=top;i++)
   cout<<S[i]<<" ";
return 1;
}

int solutie(int S[100],int top)
{
if (top==n) return 1;
if (G[S[vf][top]==1 && V[top]==0)
return 0;
}

int init(int S[100],int top)
{
S[top]=top;
cout << vf;
return 1;
}

int tipar()
{

}

int bktr()
{
top = 1;
V[vf] = 1;
init(S,top);
while (top>=1)
{
     int am;
     int este;
     do{
        am=succ(S,top);
        este=valid(S,top);
        } while (!((am&&este)||(!am)));
     if (am)   {
                    if (solutie(S,top)) { tipar(S,top);}
                                else    {
                                            top++;
                                            init(S,top);
                                          }
                  }
           else {top--;}
}
return 1;}

int main()
{
read_data();
bktr();
//DFS_IT(1); //  1 2 3 4 5
/*
Tema :
Sa se modifice DFS_IT "degenerat" in forma explicita BKTR standard

1) init
2) tipar
3) valid
4) succesor
5) solutie

while (vf>=1) {
                        int am;
                        int este;
                        do {
                             am=succesor(ST,vf);
                             este=valid(ST,vf);
                             } while(!((am&&este)||(!am)));
                        if (am) { if (solutie(ST,vf)) tipar(ST,vf);
                                                        else { vf++;
                                                                  init(ST,vf);}
                                  }
                           else vf--;
                         }

*/
}