HackerEarth Micro and Coins problem solution

by
In this HackerEarth Micro and Coins problem solution Micro was playing with a graph gifted to him by his friend on his birthday. The graph contains N vertices and M edges. All the edges are bidirectional. On each vertex of the graph there is a coin. Now Micro has to collect them all. But the game has some rules. The player has to start with some vertex. From current vertex, player can visit only those vertices which are connected to it by an edge. Also if a vertex is visited it cannot be visited again. Now Micro wants to find if he’ll be able to collect all the coins.
HackerEarth Micro and Coins problem solution

HackerEarth Micro and Coins problem solution.

#include<bits/stdc++.h>
using namespace std;

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

Second solution

#include<bits/stdc++.h>
#define nmax 10
using namespace std;
bool find_hamiltonian_paths(int adj[][nmax],int n)
{
  bool dp[nmax][1<<nmax]={0};
  int i,j,k;
  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]=1;
            break;
          }
  for(i=0;i<n;i++)
    if(dp[i][limit-1])
      return 1;
  return 0;
}
int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
    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;
    }
    find_hamiltonian_paths(adj,n)?printf("Yesn"):printf("Non");
  }
  return 0;
}