# C++ DFS solution rather than union find

• There have been union find solution around. I tried to develop a DFS solution. The idea is to first find all nodes in the cycle with DFS, then find the last edge connecting two nodes in the cycle.

``````class Solution {
public:
bool DFS_helper_cycle(unordered_map<int, unordered_multiset<int>> &graph, int node, vector<int> &visited, vector<int> &curpath, vector<int> &cyclepath) {
if(visited[node] == 1) return true;
curpath.push_back(node);
if(visited[node] == -1) {
cyclepath = curpath;
return false;
}
visited[node] = -1;
for(auto it = graph[node].begin(); it != graph[node].end(); it++) {
graph[*it].erase(graph[*it].find(node));
if(!DFS_helper_cycle(graph, *it, visited, curpath, cyclepath))
return false;
}
visited[node] = 1;
curpath.pop_back();
return true;
}
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
unordered_map<int, unordered_multiset<int>> graph;
for(int i = 0; i < edges.size(); i++) {
graph[edges[i][0]].insert(edges[i][1]);
graph[edges[i][1]].insert(edges[i][0]);
}
vector<int> cyclepath;
vector<int> visited(2001, 0);
for(auto it = graph.begin(); it != graph.end(); it++) {
if(visited[it->first] == 1) continue;
vector<int> curpath;
if(!DFS_helper_cycle(graph, it->first, visited, curpath, cyclepath))
break;
}
auto itt = find(cyclepath.begin(), cyclepath.end(), cyclepath.back());
unordered_set<int> nodeincycle(itt, cyclepath.end());
for(int i = edges.size()-1; i >= 0; i--) {
if(nodeincycle.count(edges[i][0]) > 0 && nodeincycle.count(edges[i][1]) > 0)
return edges[i];
}
return vector<int>();
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.