/*
Cititi din fisierul graf.in nr. de noduri si matricea de
adiacenta a unui graf neorientat si din fisierul
secv.in nr. de noduri si nodurile dintr-o secventa
si apoi verificati daca secventa este un lant in graful
citit.
*/
#include <iostream>
#include <fstream>

using namespace std;
int a[50][50],b[80],n,m,i,j;

void citire()
{
    ifstream f1("graf.in");
    f1>>n;
    for(i=1;i<=n;i++)
     for(j=1;j<=n;j++)
      f1>>a[i][j];
    ifstream f2("secv.in");
    f2>>m;
    for(i=1;i<=m;i++)
      f2>>b[i];
}

int lant()
{
   int k;
   k=1;
   for(i=1;i<=m-1;i++)
    if(a[b[i]][b[i+1]]==0)
      k=0;
   return k;
}

int main()
{
    citire();
    if(lant()==0)
         cout<<"Nu este lant"<<endl;
    else
         cout<<"Este lant"<<endl;

    return 0;
}







/*
n, a => listele de adiacenta
*/
#include <iostream>
using namespace std;

int n,a[50][50],i,j;

void citire()
{
    cout<<"n=";
    cin>>n;
    for(i=1;i<=n;i++)
     for(j=1;j<=n;j++)
      {
          cout<<"a["<<i<<"]["<<j<<"]=";
          cin>>a[i][j];
      }
}

void afis_listead()
{
    for(int i=1;i<=n;i++)
     {
         cout<<"Lista de adiacenta a nodului "<<i<<":"<<endl;
         for(int j=1;j<=n;j++)
           if(a[i][j]==1)
            cout<<j<<" ";
         cout<<endl;
     }
}

int main()
{
    citire();
    afis_listead();
    return 0;
}








/*
n, a=> Muchiile
*/
#include <iostream>
using namespace std;
int n,a[50][50],i,j;

void citire()
{
    cout<<"n=";
    cin>>n;
    for(i=1;i<=n;i++)
     for(j=1;j<=n;j++)
      {
          cout<<"a["<<i<<"]["<<j<<"]=";
          cin>>a[i][j];
      }
}

void afis_muchii()
{
    for(int i=1;i<=n;i++)
     {
         for(int j=1;j<=n;j++)
           if(a[i][j]==1 && i<j) //sa nu se scrie de 2 ori
            cout<<i<<" "<<j<<endl;
     }
}

int main()
{
    citire();
    afis_muchii();
    return 0;
}










/*
Cititi elementele intregi ale unei matrice
patratice si stabiliti daca poate sa fie
matricea de adiacenta a unui graf. In caz
afirmativ stabiliti daca este un graf
neorientat.
n=3
0 1 0
1 0 1  => Da
0 1 0
*/
#include <iostream>

using namespace std;

int n,a[50][50],i,j;

void citire()
{
    cout<<"n=";
    cin>>n;
    for(i=1;i<=n;i++)
     for(j=1;j<=n;j++)
      {
          cout<<"a["<<i<<"]["<<j<<"]=";
          cin>>a[i][j];
      }
}

int verifmatad()
{
    int k;
    k=1;
    for(i=1;i<=n;i++)
     if(a[i][i]!=0)
       k=0;
    for(i=1;i<=n;i++)
     for(j=1;j<=n;j++)
      if(i!=j)
       if((a[i][j]!=0)&&(a[i][j]!=1))
         k=0;
    return k;
}

int grafneor()
{
    int ok;
    ok=1;
    for(i=1;i<=n-1;i++)
      for(j=i+1;j<=n;j++)
        if(a[i][j]!=a[j][i])
          ok=0;
    return ok;
}
int main()
{
    citire();
    if(verifmatad()==0)
      cout<<"Nu este matrice de adiacenta";
    else
      {
          cout<<"Este matrice de adiacenta"<<endl;
          if(grafneor()==1)
           cout<<"Graful este neorientat";
          else
           cout<<"Graful este orientat";
      }
    return 0;
}









/*
n, m, Muchiile => a
*/
#include <iostream>
using namespace std;
int n,a[50][50],i,j,m,x,y;

void citire()
{
    cout<<"n=";
    cin>>n;
    cout<<"m=";
    cin>>m;
    for(i=1;i<=m;i++)
      {
          cout<<"x=";
          cin>>x;
          cout<<"y=";
          cin>>y;
          a[x][y]=1;
          a[y][x]=1;
      }
}

void afisare()
{
    for(int i=1;i<=n;i++)
     {
         for(int j=1;j<=n;j++)
            cout<<a[i][j]<<" ";
         cout<<endl;
     }
}

int main()
{
    citire();
    afisare();
    return 0;
}









/*
n, a=> Muchiile
*/
#include <iostream>
#include <fstream>
using namespace std;
int n,a[50][50],i,j,nr;

void citire()
{
    ifstream f("matad.in");
    f>>n;
    for(i=1;i<=n;i++)
     for(j=1;j<=n;j++)
          f>>a[i][j];
}

int numar_muchii()
{
    nr=0;
    for(int i=1;i<=n;i++)
         for(int j=i+1;j<=n;j++) //deasupra diag. princ.
           if(a[i][j]==1)
            nr++;
    return nr;
}

int main()
{
    citire();
    cout<<numar_muchii();
    return 0;
}







///Se citesc n si a
///pt. un graf neorientat.
///Sa se verifice daca este
///graful nul.
#include <iostream>
using namespace std;
int n,a[50][50],ok=1;
int main()
{
    cout << "n=";
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
          {
              cin>>a[i][j];
              if(a[i][j]!=0)
                ok=0;
          }
    ///for(int i=1;i<=n;i++)
        ///for(int j=1;j<=n;j++)
          ///if(a[i][j]!=0)
             ///ok=0;
    if(ok==1)
        cout<<"Graf nul";
    else
        cout<<"Graful nu este nul";
    return 0;
}










///Se citesc nr. de noduri
///si matricea de adiacenta
///a unui graf neorientat.
///Sa se afiseze gradul fiecarui nod.
#include <iostream>
using namespace std;
int n,a[50][50];
int grad(int x)
{
    int s=0;
    for(int j=1;j<=n;j++)
        s=s+a[x][j];
    return s;
}
int main()
{
    cout<<"n=";
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
          cin>>a[i][j];
    for(int i=1;i<=n;i++)
        cout<<grad(i)<<endl;
    return 0;
}