Problem :

https://www.hackerrank.com/challenges/find-the-nearest-clone/problem


My Solution :

#!/usr/bin/env python3


class Graph(object):
    def __init__(self):
        self.graph = {}
        self.color = {}

    def add_edge(self, u, v):
        self.graph.setdefault(u, []).append(v)

    def set_color(self, u, color):
        self.color[u] = color

    def bfs(self, s):
        distance = 0
        color = self.color[s]
        visited = [0] * (len(self.graph)+1)
        queue = []
        queue.append(s)
        visited[s] = 1
        while queue:
            s = queue.pop(0)
            distance += 1
            for t in self.graph[s]:
                if not visited[t]:
                    if self.color[t] == color:
                        return distance
                    queue.append(t)
                    visited[t] = 1
        return 10**6


def findShortest(graph_nodes, graph_from, graph_to, ids, val):
    graph = Graph()
    for u, v in zip(graph_from, graph_to):
        graph.add_edge(u, v)
        graph.add_edge(v, u)
    for u in range(1, len(ids)+1):
        graph.set_color(u, ids[u-1])
    min_distance = 10**6
    for u in range(1, graph_nodes+1):
        if graph.color[u] == val:
            min_distance = min(min_distance, graph.bfs(u))
    if min_distance == 10**6:
        return -1
    return min_distance


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)
print(ans)