In this HackerEarth Micro and Permutations problem solution Micro is having a graph having N vertices numbered from 1 to N and M edges. All the edges are bidirectional. Micro wants to find out the number of lucky permutations in the graph.
A permutation of the vertices [v1,v2,v3,...,vn] is called lucky permutation, if for every vertex vi, where 1<=i<=N - 1, there is an edge between vi and vi+1. Help Micro find out the number of lucky permutations in the graph.


HackerEarth Micro and Permutations problem solution


HackerEarth Micro and Permutations problem solution.

#include<bits/stdc++.h>

using namespace std;

int main(){
int n, m;
cin>>n>>m;
int mat[40][40]={0};
for(int i=0; i<m; i++){
int x, y;
cin>>x>>y;
mat[x][y]=mat[y][x]=1;
}
int cnt=0;
vector<int> v;
for(int i=1; i<=n; i++)
v.push_back(i);
while(true){
int i;
for(i=1; i<v.size(); i++)
if(!mat[v[i]][v[i-1]])
break;
if(i == v.size())
cnt++;
if(!next_permutation(v.begin(), v.end()))break;
}
cout<<cnt<<endl;
return 0;
}

Second solution

#include<bits/stdc++.h>
#define nmax 10
using namespace std;
int dp[nmax][1<<nmax];
int find_hamiltonian_paths(int adj[][nmax],int n)
{
int i,j,k,count=0;
for(i=0;i<n;i++)
dp[i][1<<i]=1;
int limit=1<<n;
for(i=0;i<limit;i++)
for(j=0;j<n;j++)
if(i & (1<<j))
for(k=0;k<n;k++)
if(k!=j && (i&(1<<k)) && adj[j][k] && dp[k][i^(1<<j)])
{
dp[j][i]+=dp[k][i^(1<<j)];
//break;
}
for(i=0;i<n;i++)
count+=dp[i][limit-1];
return count;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
int i,adj[nmax][nmax]={0};
for(i=0;i<m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
adj[x-1][y-1]=adj[y-1][x-1]=1;
}
cout<<find_hamiltonian_paths(adj,n);
return 0;
}