package depth_first_search;

import java.util.ArrayList;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

/**

* Created by gouthamvidyapradhan on 18/01/2018.

* 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

/ \

\_/

Solution: O(V + E) maintain a hashmap of reference nodes and build the graph by dfs

*/

public class CloneGraph {

static class UndirectedGraphNode {

int label;

List<UndirectedGraphNode> neighbors;

UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<>(); }

}

private Map<Integer, UndirectedGraphNode> map;

/**

* Main method

* @param args

* @throws Exception

*/

public static void main(String[] args) throws Exception{

UndirectedGraphNode node = new UndirectedGraphNode(0);

UndirectedGraphNode node1 = new UndirectedGraphNode(1);

UndirectedGraphNode node2 = new UndirectedGraphNode(2);

node.neighbors.add(node1);

node.neighbors.add(node2);

node1.neighbors.add(node);

node1.neighbors.add(node2);

node2.neighbors.add(node);

node2.neighbors.add(node1);

node2.neighbors.add(node2);

UndirectedGraphNode result = new CloneGraph().cloneGraph(node);

//print result

}

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {

if(node == null) return null;

map = new HashMap<>();

UndirectedGraphNode clone = new UndirectedGraphNode(node.label);

dfs(node, clone);

return clone;

}

private void dfs(UndirectedGraphNode original, UndirectedGraphNode clone){

map.put(clone.label, clone);

List<UndirectedGraphNode> oChildren = original.neighbors; //original child nodes

List<UndirectedGraphNode> cChildren = clone.neighbors; //clone child nodes

for(UndirectedGraphNode oChild : oChildren){

if(map.containsKey(oChild.label)){

//already visited node

cChildren.add(map.get(oChild.label));

} else{

//a new node

UndirectedGraphNode newChildClone = new UndirectedGraphNode(oChild.label);

cChildren.add(newChildClone);

dfs(oChild, newChildClone);

}

}

}

}