Header Ad

HackerEarth Fredo and his Birthday Gift problem solution

In this HackerEarth Fredo and his Birthday Gift problem solution It was Fredo's birthday yesterday. He got a simple graph of N vertices and M edges as one of the birthday gifts. He has been bragging about his gift to all his friends. One of his friends asked him to do the following task on the graph:

For each of the vertices in the graph, find the maximum length simple path ending at that vertex.
Being unable to solve it himself, he asks you for help. Help Fredo!
Note: Length of a simple path= number of edges in the path.
A simple path is a path in a graph which does not have repeating vertices.


HackerEarth Fredo and his Birthday Gift problem solution


HackerEarth Fredo and his Birthday Gift problem solution.

#include<bits/stdc++.h>
#define nmax 15
using namespace std;
int ans[nmax];
void find_hamiltonian_paths(int adj[nmax][nmax],int n)
{
bool dp[nmax][1<<nmax]={0};
int i,j,k;
for(i=0;i<n;i++)
{
dp[i][1<<i]=1;
ans[i]=0;
}
int limit=1<<n;
for(i=0;i<limit;i++)
{
int count=0,temp=i;
while(temp)
{
temp&=temp-1;
count++;
}
for(j=0;j<n;j++)
{
if(i & (1<<j))
{
for(k=0;k<n;k++)
if(k!=j && adj[k][j] && (i & (1<<k)) && dp[k][i^(1<<j)])
{
dp[j][i]=1;break;
}
if(dp[j][i])
ans[j]=max(ans[j],count-1);
}
}
}
for(i=0;i<n;i++)
printf("%d ",ans[i]);
printf("\n");
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m,i,adj[nmax][nmax]={0};
scanf("%d%d",&n,&m);
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);
}
return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define pb push_back
#define mk make_pair
ll power(ll a, ll b) {
ll x = 1, y = a;
while(b > 0) {
if(b%2 == 1) {
x=(x*y);
if(x>mod) x%=mod;
}
y = (y*y);
if(y>mod) y%=mod;
b /= 2;
}
return x;
}
int adj[15][15];
int dp[15][1<<15];
int n;
int func(int mask, int total) {
if(total == (1 << mask)) {
return 0;
}
if(dp[mask][total] != -1) {
return dp[mask][total];
}
int s = 0,i;
for(i = 0; i < n; i++) {
if(i != mask && total&(1<<i) && adj[i][mask] != -1) {
s = max(s,func(i,total&~(1<<mask))+1);
}
}
return dp[mask][total] = s;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int t,m,i,j,u,v;
cin>>t;
while(t--) {
cin>>n>>m;
memset(dp,-1,sizeof dp);
memset(adj,-1,sizeof adj);
while(m--) {
cin>>u>>v;
u--;
v--;
adj[u][v] = adj[v][u] = 1;
}
int x = (1<<n)-1;
for(i = 0; i < n; i++) {
cout<<func(i,x)<<" ";
}
cout<<endl;
}
return 0;
}

Post a Comment

0 Comments