# HackerEarth Micro and Permutations problem solution

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.

`#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 10using 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;}`