https://app.codesignal.com/company-challenges/ascend

mergeNodes.py

n = 10
g = [[3,7], 
 [6,2], 
 [10,4], 
 [4,8], 
 [6,8], 
 [3,1], 
 [2,9], 
 [2,8], 
 [6,9], 
 [7,8], 
 [5,10], 
 [7,2], 
 [3,2], 
 [5,1], 
 [5,6]]
v = [8, 6, 4, 10, 1]

class Node:
    def __init__(self,value) -> None:
        self.value = value
        self.childs = []
    def add_child(self,child):
        self.childs.append(child)
    def merge_with(self,nodeb):
        if nodeb.value in self.childs:
            self.childs[self.childs.index(nodeb.value)] = -nodeb.value
        for child in nodeb.childs:
            if child != self.value:
                self.childs.append(child)


def dfs(node,visited,graph,rec):
    visited[node] = True
    rec[node] = True
    print(graph[node].value,graph[node].childs)
    for child in graph[node].childs:
        if child < 0:
            continue
        if visited[child-1] == False:
            if dfs(child-1,visited,graph,rec) == True:
                return True
        elif rec[child-1] == True:
            return True
    rec[node] = False
    return False


def is_valid(n,g,v):
    nodes = [Node(value) for value in range(1,n+1)]
    visited = [False for _ in range(n)]
    rec = [ False for _ in range(n) ]
    for edge in g:
        node,child = edge
        nodes[node-1].add_child(child)
    #merge nodes
    for node in v[1:]:
         nodes[v[0]-1].merge_with(nodes[node-1])
         for idx in range(n):
             if node in nodes[idx].childs:
                 nodes[idx].childs[ nodes[idx].childs.index(node)] = v[0]
    # traverse node
    return dfs(v[0],visited,nodes,rec)
is_valid(n,g,v)