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].
#
#
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;
}