In this HackerEarth Big P and Party problem solution Big P has recently become very famous among girls .
Big P goes to a party and every girl present there wants to dance with him. However, Big P cannot dance with all of them, because there are many of them.
Now if a girl gets to dance with Big P, she considers herself to be ” 1-Lucky “. A person that dances with someone who has danced with a person who has danced with Big P considers themselves ” 2-Lucky “, and so on.
The Luckiness is defined on the basis of above mentioned rule. ( 1-Lucky -> Luckiness = 1).
HackerEarth Big P and Party problem solution.
#include <cstdio>
#include <cstdlib>
#include <queue>
#include<iostream>
using namespace std;
main() {
int numPerson, numDance;
int i, j;
cin>>numPerson>>numDance;
int gnum[numPerson];
bool adj[numPerson][numPerson];
for (i = 0; i < numPerson; i++)
{
for (j = 0; j < numPerson; j++)
{
adj[i][j] = false;
}
gnum[i] = -1;
}
for (i = 0; i < numDance; i++) {
int a, b;
cin>>a>>b;
adj[a][b] = adj[b][a] = true;
}
//BFS
gnum[0] = 0;
queue<int> q;
q.push(0);
while (!q.empty())
{
int thisPerson = q.front();
q.pop();
for (i = 1; i < numPerson; i++)
{
if (adj[i][thisPerson] && gnum[i] == -1)
{
gnum[i] = gnum[thisPerson]+1;
q.push(i);
}
}
}
for (i = 1; i < numPerson; i++) {
cout<<gnum[i]<<endl;
}
return 0;
}
Second solution
#include<stdio.h>
#include<iostream>
#include<set>
#include<vector>
#include<list>
#include<utility>
#include<stack>
#include<limits.h>
#include<algorithm>
#include<utility>
using namespace std;
vector <vector <pair<int,int> > > G(1005);
int visited[1005]={0};
vector <int> Dist(1005);
int find_minimum(int nodes)
{
int vertex,Min=INT_MAX,i;
for(i=0;i<nodes;i++)
{
if(!visited[i] && (Dist[i]<=Min))
{
Min=Dist[i];
vertex=i;
}
}
return vertex;
}
void Dijkstra(int Source,int nodes)
{
int i,j;
//Assign infinity to Dist
for(i=0;i<nodes;i++)
Dist[i]=INT_MAX;
Dist[Source]=0;
set < pair<int,int> > q;
//Set top contains minimum value by default
q.insert (make_pair (Dist[Source], Source));
while(!q.empty())
{
//Step 3.(a)
int next_node=q.begin()->second;
//Step 3.(b)
q.erase(q.begin());
for(j=0;j<G[next_node].size();j++)
{
//Step 3.(c)
int adj_node=G[next_node][j].first;
int cost=G[next_node][j].second;
if(Dist[next_node]+cost<Dist[adj_node]){
q.erase(make_pair(Dist[adj_node],adj_node));
Dist[adj_node]=Dist[next_node]+cost;
q.insert(make_pair(Dist[adj_node],adj_node));
}
}
}
}
int main()
{
//Undirected Graph
int nodes,rel,a,b,cost,i,j;
cin>>nodes>>rel;
for(i=0;i<rel;i++)
{
cin>>a>>b;
G[a].push_back(make_pair(b,1));
G[b].push_back(make_pair(a,1));
}
//source node
Dijkstra(0,nodes);
for(i=1;i<nodes;i++)
cout<<Dist[i]<<endl;
return 0;
}