# Interview preparation kit, Graph

## Find the Nearest Clone

• Thought: Run through the following steps
• (2) Traverse nodes, mark the current nodes as traversed to prevent stack overflow, if encounter the node of the same color, update the result and set res = 0 for next searching
• (3) Keep DFS until all the node has been traversed and all the function has been returned
• Analysis:
• Time complexity: O(V + E), typical graph dfs traversal
• Space complexity: O(V + E), storing the edge and node data
#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

// Complete the findShortest function below.

/*
* For the unweighted graph, <name>:
*
* 1. The number of nodes is <name>_nodes.
* 2. The number of edges is <name>_edges.
* 3. An edge exists between <name>_from[i] to <name>_to[i].
*
*/

void dfs(vector<vector <int> > edges, vector<bool> visited, vector<long> ids, int cur_id, int& res, int cur_len, int val)
{
visited[cur_id] = true;// mark current node as traversed

// if the color of current node is what we want, update the result, but NO NEED TO RETURN
// since there will be other path not visited, go to the other path will be suitable.

int n = edges[cur_id].size();// how many mnodes are "being connected" by current node?
if(ids[cur_id - 1] == val && cur_len > 0)
{
res = min(res, cur_len);
cur_len = 0;
// restart from current node

for(int i = 0; i < n; i++)
{
if(!visited[edges[cur_id][i]]) // if untraversed
{
dfs(edges, visited, ids, edges[cur_id][i], res, cur_len + 1, val);
}
}
}
else
{
// keep searching
for(int i = 0; i < n; i++)
{
if(!visited[edges[cur_id][i]]) // if untraversed
{
dfs(edges, visited, ids, edges[cur_id][i], res, cur_len + 1, val);
}
}
}
}

int findShortest(int graph_nodes, vector<int> graph_from, vector<int> graph_to, vector<long> ids, int val)
{
// init
int res = INT_MAX;
int m = graph_from.size(); // edge size
int n = ids.size(); // node size
vector<vector<int>> edges(n + 1, vector<int>()); // edge relations of node_1 -> node_2 -> node_3, n + 1 for padding one base
unordered_map<int, int> color_cnt;
vector<bool> visited(n + 1, false);

for(int i = 0; i < m; i++)
{
edges[graph_from[i]].push_back(graph_to[i]); // make the edge relations
edges[graph_to[i]].push_back(graph_from[i]); // make the edge relations
}

// find the starting node of that color
int start_id = -1;
for(int i = 0 ; i < n; i++)
{
color_cnt[ids[i]]++;
if(ids[i] == val)
{
start_id = i + 1;
}
}

// starting dfs
if(color_cnt[start_id] == 1 || start_id == -1) //only one for that color, return -1 directly or no such color
{
return -1;
}
dfs(edges, visited, ids, start_id, res, 0, val);
printf("res %d \n", res == INT_MAX ? -1 : res);
return res == INT_MAX ? -1 : res;
}