BFS: Shortest Reach in a Graph
Problem Statement :
Consider an undirected graph consisting of n nodes where each node is labeled from 1 to n and the edge between any two nodes is always of length 6. We define node s to be the starting position for a BFS. Given a graph, determine the distances from the start node to each of its descendants and return the list in node number order, ascending. If a node is disconnected, it's distance should be -1. For example, there are n = 6 nodes in the graph with a starting node s = 1 . The list of edges = [ [1,2], [2, 3],[3, 4 ], [1, 5 ] ] and each has a weight of 6 . Function Description Define a Graph class with the required methods to return a list of distances. Input Format The first line contains an integer, q, the number of queries. Each of the following q sets of lines is as follows: The first line contains two space-separated integers, n and m, the number of nodes and the number of edges. Each of the next m lines contains two space-separated integers, u and v, describing an edge connecting node u to node v. The last line contains a single integer, s, the index of the starting node. Output Format For each of the q queries, print a single line of n - 1 space-separated integers denoting the shortest distances to each of the n - 1 other nodes from starting position s. These distances should be listed sequentially by node number (i.e.1, 2 , . . . , n ), but should not include node s. If some node is unreachable from s , print -1 as the distance to that node. Sample Input 2 4 2 1 2 1 3 1 3 1 2 3 2 Sample Output 6 6 -1 -1 6
Solution :
Solution in C :
In C :
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int addqueue(int t, int q[],int v);
int main()
{
int q;
scanf("%d",&q);
while(q--)
{
int n,m;
scanf("%d %d",&n,&m);
int a[n+1][n+1];
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
a[i][j]=-1;
}
}
while(m--)
{
int u,v;
scanf("%d %d",&u,&v);
a[u][v]=6;
a[v][u]=6;
}
int s;
scanf("%d",&s);
int ans[n+1];
ans[0]=0;
ans[s]=0;
for(int i=1;i<=n;i++)
{
if(i!=s)
ans[i]=-1;
}
int queue[n];
queue[0]=s;
int c=0,top=1;
while(c!=top)
{
for(int i=1;i<=n;i++)
{
if(a[queue[c]][i]==6)
{
if(addqueue(top,queue,i))
{
queue[top]=i;
top++;
// ans[i]=6*(c+1);
ans[i]=6+ans[queue[c]];
}
}
}
c++;
}
for(int i=1;i<=n;i++)
{
if(i==s)
continue;
else
printf("%d ",ans[i]);
} printf("\n");
}
return 0;
}
int addqueue(int t, int q[],int v)
{
for(int i=0;i<t;i++)
{
if(q[i]==v)
return 0;
}
return 1;
}
Solution in C++ :
In C++ :
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <list>
#include <queue>
using namespace std;
class Graph {
public:
Graph(int n) {
data.resize(n);
}
void add_edge(int u, int v) {
data[u].push_back(v);
data[v].push_back(u);
}
vector<int> shortest_reach(int start) {
vector<int> result(data.size(), -1);
std::queue<int> q;
q.push(start);
result[start] = 0;
while(!q.empty())
{
int v = q.front();
q.pop();
for(auto it = data[v].begin(); it != data[v].end(); it++)
{
if (result[*it] < 0)
{
result[*it] = result[v]+6;
q.push(*it);
}
}
}
//for(int i(start); i < data.size()-1; i++)
// result[i] = result[i+1];
//result.resize(data.size()-1);
return result;
}
private:
std::vector<std::list<int> > data;
};
int main() {
int queries;
cin >> queries;
for (int t = 0; t < queries; t++) {
int n, m;
cin >> n;
// Create a graph of size n where each edge weight is 6:
Graph graph(n);
cin >> m;
// read and set edges
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--, v--;
// add each edge to the graph
graph.add_edge(u, v);
}
int startId;
cin >> startId;
startId--;
// Find shortest reach from node s
vector<int> distances = graph.shortest_reach(startId);
for (int i = 0; i < distances.size(); i++) {
if (i != startId) {
cout << distances[i] << " ";
}
}
cout << endl;
}
return 0;
}
Solution in Java :
In Java :
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static class Graph {
private int V;
private LinkedList<Integer> [] G;
public Graph(int size) {
this.V = size;
this.G = new LinkedList[V];
for(int v = 0; v < V; v++)
G[v] = new LinkedList<>();
}
public void addEdge(int first, int second) {
G[first].add(second);
G[second].add(first);
}
public int[] shortestReach(int startId) { // 0 indexed
boolean [] visited = new boolean[V];
Queue<Integer> q = new LinkedList<>();
q.add(startId);
visited[startId] = true;
int size = 1;
int distance = 6;
int [] distTo = new int[V];
Arrays.fill(distTo, -1);
while(!q.isEmpty()) {
int v = q.poll();
for(int w : G[v]) {
if(!visited[w]) {
visited[w] = true;
distTo[w] = distance;
q.add(w);
}
}
if(--size == 0) {
size = q.size();
distance+=6;
}
}
return distTo;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int queries = scanner.nextInt();
for (int t = 0; t < queries; t++) {
// Create a graph of size n where each edge weight is 6:
Graph graph = new Graph(scanner.nextInt());
int m = scanner.nextInt();
// read and set edges
for (int i = 0; i < m; i++) {
int u = scanner.nextInt() - 1;
int v = scanner.nextInt() - 1;
// add each edge to the graph
graph.addEdge(u, v);
}
// Find shortest reach from node s
int startId = scanner.nextInt() - 1;
int[] distances = graph.shortestReach(startId);
for (int i = 0; i < distances.length; i++) {
if (i != startId) {
System.out.print(distances[i]);
System.out.print(" ");
}
}
System.out.println();
}
scanner.close();
}
}
Solution in Python :
In Python3 :
def find_all_dists(g, s):
r = {}
ss = {}
for n in g[s]:
r[n] = 1
ss[n] = 1
arr = [r]
ss[s] = 0
while True:
r = {}
pr = arr[-1]
for key, c in pr.items():
for ne in g[key]:
if ne not in ss or ss[ne] > c+1:
if ne in r and r[ne] <= c+1:
continue
r[ne] = c+1
ss[ne] = c+1
if r == {}:
break
arr.append(r)
return ss
t = int(input())
for i in range(t):
n,m = [int(value) for value in input().split()]
graph = {}
for i in range(n+1):
graph[i+1] = []
for i in range(m):
u,v = [int(x) for x in input().split()]
graph[u].append(v)
graph[v].append(u)
s = int(input())
ss = find_all_dists(graph, s)
#print(ss)
res = []
for i in range(1,n+1):
if i == s:
continue
if i not in ss:
res.append('-1')
else:
res.append(str(ss[i] * 6))
print(" ".join(res))
View More Similar Problems
Array-DS
An array is a type of data structure that stores elements of the same type in a contiguous block of memory. In an array, A, of size N, each memory location has some unique index, i (where 0<=i<N), that can be referenced as A[i] or Ai. Reverse an array of integers. Note: If you've already solved our C++ domain's Arrays Introduction challenge, you may want to skip this. Example: A=[1,2,3
View Solution →2D Array-DS
Given a 6*6 2D Array, arr: 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 An hourglass in A is a subset of values with indices falling in this pattern in arr's graphical representation: a b c d e f g There are 16 hourglasses in arr. An hourglass sum is the sum of an hourglass' values. Calculate the hourglass sum for every hourglass in arr, then print t
View Solution →Dynamic Array
Create a list, seqList, of n empty sequences, where each sequence is indexed from 0 to n-1. The elements within each of the n sequences also use 0-indexing. Create an integer, lastAnswer, and initialize it to 0. There are 2 types of queries that can be performed on the list of sequences: 1. Query: 1 x y a. Find the sequence, seq, at index ((x xor lastAnswer)%n) in seqList.
View Solution →Left Rotation
A left rotation operation on an array of size n shifts each of the array's elements 1 unit to the left. Given an integer, d, rotate the array that many steps left and return the result. Example: d=2 arr=[1,2,3,4,5] After 2 rotations, arr'=[3,4,5,1,2]. Function Description: Complete the rotateLeft function in the editor below. rotateLeft has the following parameters: 1. int d
View Solution →Sparse Arrays
There is a collection of input strings and a collection of query strings. For each query string, determine how many times it occurs in the list of input strings. Return an array of the results. Example: strings=['ab', 'ab', 'abc'] queries=['ab', 'abc', 'bc'] There are instances of 'ab', 1 of 'abc' and 0 of 'bc'. For each query, add an element to the return array, results=[2,1,0]. Fun
View Solution →Array Manipulation
Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array. Example: n=10 queries=[[1,5,3], [4,8,7], [6,9,1]] Queries are interpreted as follows: a b k 1 5 3 4 8 7 6 9 1 Add the valu
View Solution →