<s> """<STR_LIT>""" <EOL> __author__ = '<STR_LIT>' <EOL> class UndirectedGraphNode : <EOL> def __init__ ( self , x ) : <EOL> self . label = x <EOL> self . neighbors = [ ] <EOL> def __repr__ ( self ) : <EOL> return repr ( self . label ) <EOL> class Solution : <EOL> def cloneGraph_TLE ( self , node ) : <EOL> """<STR_LIT>""" <EOL> return self . clone_graph_visited ( node , set ( ) ) <EOL> def clone_graph_visited ( self , node , visited_set ) : <EOL> """<STR_LIT>""" <EOL> if not node : <EOL> return <EOL> visited_set . add ( node ) <EOL> neighbors_cloned = [ self . clone_graph_visited ( neighbor , set ( visited_set ) ) for neighbor in node . neighbors if neighbor not in visited_set ] <EOL> node_cloned = UndirectedGraphNode ( node . label ) <EOL> for neighbor_cloned in neighbors_cloned : <EOL> if neighbor_cloned not in visited_set : <EOL> neighbor_cloned . neighbors . append ( node_cloned ) <EOL> node_cloned . neighbors = neighbors_cloned <EOL> return node_cloned <EOL> def cloneGraph ( self , node ) : <EOL> """<STR_LIT>""" <EOL> if not node : <EOL> return <EOL> original2copy = { } <EOL> q = [ node ] <EOL> clone = UndirectedGraphNode ( node . label ) <EOL> original2copy [ node ] = clone <EOL> while q : <EOL> cur = q . pop ( ) <EOL> for neighbor in cur . neighbors : <EOL> if neighbor in original2copy : <EOL> original2copy [ cur ] . neighbors . append ( original2copy [ neighbor ] ) <EOL> else : <EOL> q . append ( neighbor ) <EOL> clone_neighbor = UndirectedGraphNode ( neighbor . label ) <EOL> original2copy [ neighbor ] = clone_neighbor <EOL> original2copy [ cur ] . neighbors . append ( original2copy [ neighbor ] ) <EOL> return original2copy [ node ] <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> lst = [ UndirectedGraphNode ( i + <NUM_LIT:1> ) for i in range ( <NUM_LIT:3> ) ] <EOL> for item in lst : <EOL> item . neighbors = list ( lst ) <EOL> item . neighbors . remove ( item ) <EOL> cloned = Solution ( ) . cloneGraph ( lst [ <NUM_LIT:0> ] ) <EOL> assert cloned . neighbors [ <NUM_LIT:0> ] . label in ( <NUM_LIT:2> , <NUM_LIT:3> ) <EOL> assert cloned . neighbors [ <NUM_LIT:1> ] . label in ( <NUM_LIT:2> , <NUM_LIT:3> ) </s>
