C++ DFS solution rather than union find


  • 0
    J

    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>();
        }
    };
    

Log in to reply
 

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