In this HackerRank Find the nearest clone Interview preparation kit problem there is a connected undirected graph where each of the nodes is a color. Given a color, find the shortest path connecting any two nodes of that color.
Problem solution in Python programming.
#!/bin/python3
import math
import os
import random
import re
import sys
# Complete the findShortest function below.
#
# For the weighted graph, <name>:
#
# 1. The number of nodes is <name>_nodes.
# 2. The number of edges is <name>_edges.
# 3. An edge exists between <name>_from[i] to <name>_to[i].
#
#
def dfsrec(adj,s,visited,count):
count += 1
visited[s] = 1
if ids[s-1]==val:
return count
else:
temp = -1
for u in adj[s]:
if visited[u]==0:
temp = dfsrec(adj,u,visited,count)
return temp
def findShortest(graph_nodes, graph_from, graph_to, ids, val):
#return -1 #one line code to pass all hidden test cases
# print("nodes",graph_nodes)
# print("from",graph_from)
# print("to",graph_to)
#print("id",ids)
adj = dict()
for i in range(len(graph_from)):
if graph_from[i] in adj:
#print("1")
adj[graph_from[i]].append(graph_to[i])
else:
#print("2")
adj[graph_from[i]] = [graph_to[i]]
if graph_to[i] in adj:
#print("3")
adj[graph_to[i]].append(graph_from[i])
else:
#print("4")
adj[graph_to[i]] = [graph_from[i]]
#print("adj",adj)
f = 0
for i in range(len(ids)):
if ids[i]==val:
f = 1
for adjacent in adj[i+1]:
print("inside 1 for")
if ids[adjacent-1]==val:
return 1
else:
l = []
visited = [0]*(graph_nodes+1)
visited[i+1] = 1
for adjacent in adj[i+1]:
print("inside 2 for")
variable = 0
count = dfsrec(adj,adjacent,visited,variable)
l.append(count)
print("list",l)
minn = 999999
flag = 0
for i in l:
if i!=-1 and i<minn:
flag = 1
minn = i
if flag==1:
return minn
else:
return -1
if f==0:
return -1
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
graph_nodes, graph_edges = map(int, input().split())
graph_from = [0] * graph_edges
graph_to = [0] * graph_edges
for i in range(graph_edges):
graph_from[i], graph_to[i] = map(int, input().split())
ids = list(map(int, input().rstrip().split()))
val = int(input())
ans = findShortest(graph_nodes, graph_from, graph_to, ids, val)
fptr.write(str(ans) + 'n')
fptr.close()
Problem solution in Java Programming.
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
public class Solution {
static int findShortest(int graphNodes, int[] graphFrom, int[] graphTo, int[] ids, int val) {
LinkedList<Integer>[] map = new LinkedList[graphNodes];
HashMap<Integer, Integer> distances = new HashMap();
for(int i = 0 ; i < graphNodes; i++){
map[i] = new LinkedList<Integer>();
}
for(int i = 0; i < graphFrom.length; i++){
map[graphFrom[i] - 1].add(graphTo[i]);
map[graphTo[i] - 1].add(graphFrom[i]);
}
Queue<Integer> queue = new LinkedList();
for(int i = 0; i < ids.length; i++){
if(ids[i] == val){
queue.add(i + 1);
distances.put(i + 1, 0);
}
}
if(queue.size() < 2){
return -1;
}
HashSet<Integer> seen = new HashSet();
while(queue.size() > 0){
int current = queue.poll();
seen.add(current);
for(int a : map[current - 1]){
if(distances.containsKey(a) && !seen.contains(a)){
return distances.get(a) + distances.get(current) + 1;
}
else {
queue.add(a);
distances.put(a, distances.get(current) + 1);
}
}
}
return -1;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
String[] graphNodesEdges = br.readLine().split(" ");
int graphNodes = Integer.parseInt(graphNodesEdges[0].trim());
int graphEdges = Integer.parseInt(graphNodesEdges[1].trim());
int[] graphFrom = new int[graphEdges];
int[] graphTo = new int[graphEdges];
for (int i = 0; i < graphEdges; i++) {
String[] graphFromTo = br.readLine().split(" ");
graphFrom[i] = Integer.parseInt(graphFromTo[0].trim());
graphTo[i] = Integer.parseInt(graphFromTo[1].trim());
}
int[] ids = new int[graphNodes];
String[] idsItems = br.readLine().split(" ");
for (int i = 0; i < graphNodes; i++) {
int idsItem = Integer.parseInt(idsItems[i]);
ids[i] = idsItem;
}
int val = Integer.parseInt(br.readLine().split(" ")[0]);
br.close();
int ans = findShortest(graphNodes, graphFrom, graphTo, ids, val);
bufferedWriter.write(String.valueOf(ans));
bufferedWriter.newLine();
bufferedWriter.close();
}
}
Problem solution in C++ programming.
#include <bits/stdc++.h> #define MAX 1000003 using namespace std; vector<int> v[MAX]; bool visit[MAX]; int a[MAX],c,id; void bfs(int i) { memset(visit, false, sizeof visit); queue<pair<int,int> > q; pair<int,int> p; q.push({i,0}); visit[i]=true; while(!q.empty()) { p=q.front(); q.pop(); for(auto x: v[p.first]) { if(!visit[x]) { if(a[x] == id) { c=p.second+1; return; } visit[x]=true; q.push({x,p.second+1}); } } } } int main() { int n,m,i,x,y; cin>>n>>m; for(i=0;i<m;++i) { cin>>x>>y; x-=1,y-=1; v[x].push_back(y); v[y].push_back(x); } for(i=0;i<n;++i) { cin>>a[i]; } cin>>id; int ans=1e9; for(i=0;i<n;++i) { if(a[i]==id) { c=1e9; bfs(i); ans=min(ans, c); } } if(ans==1e9) { ans=-1; } cout<<ans<<endl; return 0; }
For Java solution, you need to check that the node was not visited before prior to adding it to the queue, so
> else {
> queue.add(a);
becomes
> else if (!seen.contains(a)) {
> queue.add(a);