# Breadth First Search: Shortest Reach HackerRank Solution C, CPP, Python

Consider an undirected graph where each edge weighs 6 units. Each of the nodes is labeled consecutively from 1 to n.

You will be given a number of queries. For each query, you will be given a list of edges describing an undirected graph. After you create a representation of the graph, you must determine and report the shortest distance to each of the other nodes from a given starting position using the breadth-first search algorithm (BFS). Return an array of distances from the start node in node number order. If a node is unreachable, return  for that node.

Example
The following graph is based on the listed inputs:

// number of nodes
// number of edges

// starting node

All distances are from the start node . Outputs are calculated for distances to nodes  through . Each edge is  units, and the unreachable node  has the required return distance of .

Function Description

Complete the bfs function in the editor below. If a node is unreachable, its distance is .

bfs has the following parameter(s):

• int n: the number of nodes
• int m: the number of edges
• int edges[m]: start and end nodes for edges
• int s: the node to start traversals from

Returns
int[n-1]: the distances to nodes in increasing node number order, not including the start node (-1 if a node is not reachable)

Input Format

The first line contains an integer , the number of queries. Each of the following  sets of lines has the following format:

• The first line contains two space-separated integers  and , the number of nodes and edges in the graph.
• Each line  of the  subsequent lines contains two space-separated integers,  and , that describe an edge between nodes  and .
• The last line contains a single integer, , the node number to start from.

Sample Input

2
4 2
1 2
1 3
1
3 1
2 3
2


Sample Output

6 6 -1
-1 6


Explanation

We perform the following two queries:

1. The given graph can be represented as:
where our start node, , is node . The shortest distances from  to the other nodes are one edge to node , one edge to node , and an infinite distance to node  (which it is not connected to). We then return an array of distances from node  to nodes , and  (respectively): .
2. The given graph can be represented as:

where our start node, , is node . There is only one edge here, so node  is unreachable from node  and node  has one edge connecting it to node . We then return an array of distances from node  to nodes , and  (respectively): .

Note: Recall that the actual length of each edge is , and we return  as the distance to any node that is unreachable from .

### Breadth First Search: Shortest Reach HackerRank Solution C

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

#define FROM 0
#define TO 1
#define DISTANCE 0
#define STATUS 1
#define SPENT 0
#define PENDING 1
#define GAP 6

int main() {

int cases, nodes, edges, active, i, origin;
int node[1000+1];		// [node][distance / status]
int edge[1000*(1000-1)/2+1];	// [edge][from node / to node]

scanf("%d", &cases);

while(cases--){

scanf("%d%d", &nodes, &edges);

for(i=1; i <= edges; i++){
scanf("%d%d", &edge[i][FROM], &edge[i][TO]);
}

for(i=1; i <= nodes; i++){
node[i][DISTANCE] = -1;
node[i][STATUS] = PENDING;
}

scanf("%d", &origin);
active = origin;
node[origin][DISTANCE] = 0;
unsigned int min;
while(active){

active = 0;
min = -1;
for(i=1; i <= nodes; i++){
if(node[i][STATUS]==PENDING && node[i][DISTANCE]!=-1 && node[i][DISTANCE]<min){
min = node[i][DISTANCE];
active = i;
}
}

for(i=1; i<=edges; i++){ //originally thought it was a directed graph :/
if(edge[i][FROM]==active){
if(node[edge[i][TO]][DISTANCE]>node[edge[i][FROM]][DISTANCE]+GAP || node[edge[i][TO]][DISTANCE]==-1){
node[edge[i][TO]][DISTANCE]=node[edge[i][FROM]][DISTANCE]+GAP;
}
}
if(edge[i][TO]==active){
if(node[edge[i][FROM]][DISTANCE]>node[edge[i][TO]][DISTANCE]+GAP || node[edge[i][FROM]][DISTANCE]==-1){
node[edge[i][FROM]][DISTANCE]=node[edge[i][TO]][DISTANCE]+GAP;
}
}
}

node[active][STATUS] = SPENT;

}

for(i=1; i<=nodes; i++){
if(i!=origin)printf("%i ", node[i][DISTANCE]);
}

printf("\n");
}

return 0;
}

// some day I'm going to look back on this and want to smack myself

### Breadth First Search: Shortest Reach HackerRank Solution CPP

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cctype>
#include <limits>
#include <fstream>

using namespace std;
typedef vector<string> vs;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<vector<int> > vvi;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define DEC(i,a,b) for(int i=(a); i>=b; --i)
#define FORV(v,i) for(int i=0;i<v.size();++i)
#define FORD(v,i) for(int i=v.size()-1;i>=0;--i)
#define all(c) (c).begin(),(c).end()
#define sz(c) int((c).size())
#define pb push_back
#define ull unsigned long long
#define ll long long
#define MOD 1000000007ULL

void bfs(vector<set<int> > &V,int &S,stringstream &ss)
{
vector<bool> A(V.size(),false);
vi D(V.size(),-1);
D[S] = 0;
queue<int> Q;
Q.push(S);
//ss<<"size:"<<V[S].size()<<"\n";
A[S] = true;
while(!Q.empty())
{
int f = Q.front(); Q.pop();
//ss<<f<<","<<V[f].size()<<":";
for(set<int>::iterator it = V[f].begin();
it != V[f].end() ; ++it)
{
int p = *it;
if(!A[p])
{
//ss<<p<<",";
D[p] = D[f] + 1;
/*
int v = D[f] + 1;
if( v < D[p])
D[p] = D[f] + 1;
*/
A[p] = true;
Q.push(p);
}
}
//ss<<"\n";
}
//ss<<"\n";

//sort(all(D));
//int C = 0;
FORV(D,i)
{
if(D[i] == -1)
ss<<-1<<" ";
else if(D[i] > 0)
ss<<(D[i]*6)<<" ";
}
ss<<"\n";
//FOR(i,0,C)
//	ss<<-1<<" ";
}

int main()
{
int t;
ios_base::sync_with_stdio(false);
cin>>t;
stringstream ss;
FOR(i,0,t)
{
int n,m;
cin>>n>>m;
vector<set<int> > V(n,set<int>());
FOR(j,0,m)
{
int a,b;
cin>>a>>b;
a--;
b--;
V[a].insert(b);
V[b].insert(a);
}
int S;
cin>>S;
S--;
bfs(V,S,ss);
}
cout<<ss.str();
return 0;
}

### Breadth First Search: Shortest Reach HackerRank Solution Python

# Enter your code here. Read input from STDIN. Print output to STDOUT
import sys

def solve(n,r,s):
G=[[] for _ in range(n+1)]
for [i,j] in r:
if not((i in G[j]) | (i==j)):
G[i].append(j)
G[j].append(i)
done=[]
ndone=[s]
todo=G[s]
L=[-1 for _ in range(n+1)]
L[s]=0
for i in G[s]:
L[i]=1
while ndone!=done:
done=list(ndone)
ntodo=[]
for i in todo:
for j in G[i]:
if not((j in done) | ((j in ntodo) | (j in todo))):
L[j]=L[i]+1
ntodo.append(j)
ndone+=list(todo)
todo=list(ntodo)
st=""
for i in (L[1:s]+L[s+1:]):
if i!=-1:
st+=str(6*i)+" "
else:
st+=str(i)+" "
return st

T=int(raw_input())
for _ in range(T):
[n,m]=map(int,raw_input().strip().split())
r=[]
for _ in range(m):
r.append(map(int,raw_input().strip().split()))
s=int(raw_input())
print(solve(n,r,s))