GT spanning tree

 #include <bits/stdc++.h>

#define INF INT_MAX

#define all(x) x.begin(),x.end()

#define rall(x) x.rbegin(),x.rend()

using namespace std;

void tree(vector<int> prufer,int n){

 //For Tracking the prufer code as well as node's visit

 vector<bool>check(n,true),visit(n,true);

 //All the nodes in graphs

 vector<int> nodes(n);

 for(int i=0; i<n; i++){

 nodes[i]=i+1;

 if(i<n-2)

 check[prufer[i]-1]=false;

 }

 //Nested loop to make edge between prufer and nodes

 for(int i=0; i<prufer.size(); i++){

 for(int j=0; j<n; j++){

 //if smallest label node not in prufer is matched 

then remove both (i.e. x->y x from prufer and y from 

nodes)

 if(check[j]){

 //(Note here we are not removing but marking 

it visit true)

 cout<< prufer[i] << " --- " << nodes[j];

 visit[j]=false;

 check[j]=false;

 break;

 }

 }cout<<'\n';

 }

 //For Remaining two nodes

 for(int i=0; i<n ;i++){

 //if remaining node is in Prufer

 if(visit[i]){

 for(int j=i+1; j<n; j++){

 // If remaining nodes in Nodes

 if( visit[j]){

 cout<<nodes[i] << " --- " << nodes[j];

 break;

 }

 }

 break;

 }

 }

 cout<<'\n';

}

//---------------------------Generate all possible codes------

----------------//

void generate(int index,int n,vector<vector<int>> 

&ans,vector<int> &prufer){

 //-------------------Base condition-------------//

 if(index==n-2){

 ans.push_back(prufer);

 return;

 }

 //-----------Increment index for every child----//

 for (int i = 1; i <= n; i++)

 {

 prufer[index]=i;

 generate(index+1,n,ans,prufer);

 }

}

//-----------------Main Driver function----------------------

//

int main()

{

 int n,x;

 string pt="--------------------\n";

 cout<<pt<<"Please enter the number of vertices in 

complete graph : ";

 cin>>n;

 cout<<"Total number of spanning tree = n^(n-2) = 

"<<pow(n,n-2)<<endl;

 //--------------All possible prufer codes----------//

 vector<vector<int>> prufers;

 vector<int> prufer(n-2,0);

 cout<<pt;

 generate(0,n,prufers,prufer);

 //============Print all Spanning 

Tree==============//

 for (int i = 0; i < prufers.size(); i++)

 {

 cout<<pt<<"Spanning Tree_"<<i+1<<"\n"<<pt;

 tree(prufers[i],n);

 }

 return 0;

}