# HackerRank Find the nearest clone Interview preparation kit solution

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].
#
#
count += 1
visited[s] = 1
if ids[s-1]==val:
return count
else:
temp = -1
for u in adj[s]:
if visited[u]==0:

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)

for i in range(len(graph_from)):
if graph_from[i] in adj:
#print("1")
else:
#print("2")

if graph_to[i] in adj:
#print("3")
else:
#print("4")

f = 0
for i in range(len(ids)):
if ids[i]==val:
f = 1
print("inside 1 for")
return 1

else:
l = []
visited = [0]*(graph_nodes+1)
visited[i+1] = 1
print("inside 2 for")
variable = 0
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) {
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++){
}

Queue<Integer> queue = new LinkedList();
for(int i = 0; i < ids.length; i++){
if(ids[i] == val){
distances.put(i + 1, 0);
}
}

if(queue.size() < 2){
return -1;
}
HashSet<Integer> seen = new HashSet();
while(queue.size() > 0){
int current = queue.poll();

for(int a : map[current - 1]){
if(distances.containsKey(a) && !seen.contains(a)){
return distances.get(a) + distances.get(current) + 1;
}
else {
distances.put(a, distances.get(current) + 1);
}
}
}
return -1;
}

public static void main(String[] args) throws IOException {
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;
}```

1. For Java solution, you need to check that the node was not visited before prior to adding it to the queue, so

> else {

becomes

> else if (!seen.contains(a)) {