BFS

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

class Graph
{
  private:
  bool orient;
  int n, **arr, **vse_rebra, shet_reber, comp, *path_comp, *Lev;

  public:
  Graph (int **matrix, int x, int shet)
  {
    n = x;
    arr = matrix;
    shet_reber = shet;
  }
  void spisok ();
  void get_spisok_reber();
  int BFS(int v, int u);
  int poisk_path(int v, int u);
  void path(int v, int u);
};

void Graph::spisok ()
  {
    int shet = 0;

     vse_rebra = new int*[shet_reber];

     for ( int i = 0; i < shet_reber; i++)
       vse_rebra[i] = new int[2];

    for (int i =0; i < n; i++)
     for (int j = i; j < n; j++)
     if (arr[i][j] == 1)
     {
       vse_rebra[shet][0] = i+1;
       vse_rebra[shet][1] = j+1;
       shet++;
     }
  }

void Graph::path(int v, int u)
{
  int razmer = Lev[u];
  path_comp = new int[razmer];

  path_comp[razmer - 1] = u+1;

  for (int i = razmer - 2; i >= 0; i--)
    for (int j = 0; j < n; j++)
      if (Lev[j] == i+1 && poisk_path(j, path_comp[i+1]-1) > 0)
        path_comp[i] = j+1;

  for ( int i = 0; i < razmer; i++)
   cout << path_comp[i] << " ";
}

int Graph::poisk_path(int v, int u)
{
  int shet, x, *path = new int[n], dlina = 0;

  queue<int> Que;

  for (shet = 0; shet < n; shet++)
    {
      path[shet] = 0;
    }

  path[v] = 1;
  Que.push(v);

  while (!Que.empty())
   {
     shet = Que.front();
     Que.pop();
    for (x = 0; x < n; x++)
      if (arr[shet][x] != 0 && path[x] == 0)
      {
        path[x] = path[shet] + 1;
        dlina++;
        Que.push(x);
      }
   }

 if (path[u] == 0)
   dlina = -1;
    else if (u == v)
     dlina = 0;

  return dlina;
}

int Graph::BFS(int v, int u)
{
  int shet, x, dlina = 0;
  Lev = new int[n];

  queue<int> Que;

  for (shet = 0; shet < n; shet++)
    {
      Lev[shet] = 0;
    }

  Lev[v] = 1;
  Que.push(v);

  while (!Que.empty())
   {
     shet = Que.front();
     Que.pop();
    for (x = 0; x < n; x++)
      if (arr[shet][x] != 0 && Lev[x] == 0)
      {
        Lev[x] = Lev[shet] + 1;
        dlina++;
        Que.push(x);
      }
   }

 if (Lev[u] == 0)
   dlina = -1;
    else if (u == v)
     dlina = 0;
     else dlina = Lev[u]-1;

  return dlina;
}

int main()
{
 int n, shet_reber = 0, v, u;
 cin >> n;

int **arr = new int*[n];

for ( int i = 0; i < n; i++)
     arr[i] = new int[n];

for (int i =0; i < n; i++)
  for (int j =0; j < n; j++)
     {
       cin >> arr[i][j];
        if (arr[i][j] == 1)
         shet_reber++;
     }

 shet_reber /= 2;

 Graph object(arr, n, shet_reber);

 cin >> v >> u;

 int dlina = object.BFS(v-1, u-1);

 cout << dlina << endl;

 if (dlina > 0)
  object.path(v-1, u-1);
}