include iostream include time include vector using namespace std void

#include <iostream>
#include <time.h>
#include <vector>
using namespace std;

void shirina(bool *pas, int u, int **mat, int n);

int main(){
 setlocale(0, "");
	int n,start,i,j;
	cout << "Введите количество вершин: " ;
	cin >> n;
	cout << endl;
	bool *vis=new bool[n];
	srand(time(NULL));
	int **mat = new int*[n];

	for ( i = 0; i < n ; i ++)
	{
	   mat[i] = new int[n];
	}

  for(i=0;i<n;i++)
	{
		for(j=0;j<i;j++)
		{
			mat[i][j]=mat[j][i] = rand()%2;
			if(mat[i][j]) mat[i][j]=mat[j][i] = rand()%2;
			if(mat[i][j]) mat[i][j]=mat[j][i] = rand()%2;
			//if(mat[i][j]) mat[i][j]=mat[j][i] = rand()%2;
		}mat[i][i]=0;
	}

   for ( i = 0; i < n ; i++)
   {
		   for ( j = 0; j <n; j++)
			{
			   mat[i][j] = mat[j][i];
			   mat[i][i] = 0;
		    } 
   }
        cout<<"Матрица: "<<endl;
               for (i=0; i<n; i++){
				   vis[i]=false;
				   for (j=0; j<n; j++)
					   cout  << " " << mat[i][j];
				   cout<<endl;
			   }
         cout<<"Введите стартовую вершину: ";
         cin>>start;
       //  cout<<"Путь: " << endl;
		 shirina(vis, start, mat, n);


		 delete []vis;	   
		 for ( i = 0; i < n; i++)
			   {
				   delete[] mat[i];
			   }
			   delete[] mat;
			    return 0;
}
void shirina(bool *pas, int u, int **mat, int n)
{
	vector <int> par;
	int i = 0,j = 0;
	int *q=new int[n];
	int **skelet = (int**)calloc(n, sizeof(int*));
	int * d = (int *) calloc(n, sizeof(int));
	int count = 0, head = 0;
	for (i=0; i<n; i++)
	{
		skelet[i] = (int*)calloc(n, sizeof(int));
		q[i]=0;
	}

	q[count++]=u;
	pas[u]=true;
	while (head<count)
	{
		u=q[head++];
		par.push_back(u);
		for (i=0; i<n; i++)
			if (mat[u][i] && !pas[i])
			{
				q[count++]=i;
				d[i] = d[u] + 1;
				skelet[u][i] = skelet[i][u] = 1;
				pas[i]=true;
			}
	}
	bool done = false;
	int dd = 0;
	while (!done)
	{
		done = true;
		cout << " [ ";
		for (int i = 0; i<n; ++i)
		{
			if (d[i] == dd && pas[i])
			{
				cout << i << ' ';
			}
			if (d[i] == dd + 1) done = false;
		}
		cout << " ] ";
		if (!done) cout << endl;
		++dd;
	}
	cout << endl;
	vector <int> :: iterator r;
	cout << "Каркас: \n" ;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cout << skelet[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "\n";
	//for ( r = par.begin(); r < par.end(); r++)
///	{
		//cout << *r << " ";
	//}
	cout << endl;

	free(d);
	delete []q;
}