Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
  • Work with US
Programmingoneonone
Programmingoneonone

HackerEarth Micro and Coins problem solution

YASH PAL, 31 July 2024
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;
}
coding problems solutions

Post navigation

Previous post
Next post

Related website

The Computer Science

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes