"""
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.


OJ's undirected graph serialization:
Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/
"""

from collections import deque

from implementations.graph import UndirectedGraphNode


def clone_graph(node):
    if node is None:
        return None

    start = UndirectedGraphNode(node.label)
    queue = deque([(node, start)])
    visited = set()

    while len(queue) > 0:
        item, cloned = queue.popleft()
        if item not in visited:
            visited.add(item)
            for neigh in item.neighbors:
                if neigh not in visited:
                    neigh_cloned = UndirectedGraphNode(neigh.label)
                    cloned.neighbors.append(neigh_cloned)
                    neigh_cloned.neighbors.append(cloned)
                    queue.append((neigh, neigh_cloned))

    return start


if __name__ == '__main__':
    g = UndirectedGraphNode(-1)
    g.neighbors = [UndirectedGraphNode(1)]

    clone_graph(g)
