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 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;
}

coding problems solutions