Interesting C++ DFS Solution with o(n) time complexity (Approach #1 DFS is o(N^2))
Using DFS to detect whether a graph has a circle or not is very classic, just use a vector visited to record three different status of node (0 means not visited
Using DFS to detect whether a graph has a circle or not is very classic, just use a vector visited<int> to record three different status of node (0 means not visited, 1 means visiting, 2 means already visited and there\'s no circle), so when we are running the dfs, we found out a node visited value is 1, then it means there\'s a circle.\n\nWell, the solution for this problem is similiar, the only difference is we need to mark all nodes inside the circle to 1 and ends the recursion to stop it from changing to 2, while marking all nodes outside the circle to 2.\n\nThe problem is, assume parent node is outside of the circle and we set it to 1 and keep running the dfs with one of it\'s children node, what if that children node is inside a circle and the dfs returns false? If we terminate dfs immediately, then the parent node value will always be 1; but if we don\'t terminate dfs, then all nodes inside the circle will become 2 eventually. \n\nSo instead, we need to record that specific node to a different value to let the parent node know. Imagine we encounter the first node of the circle, we mark it to 1, and run the dfs and encounter that node again, we will see that node visited value already becomes 1, we set it to 4; and recursively when we are back from the stack to that node, if it\'s 4, we set it to 3(make it even); after that it will go back to parent node. If the parent node knows one of it\'s children node visited value is 3, it keeps traversing other children node even if the dfs returns false.\n\nEventually, all the nodes visited value will be 1 or 2 or 3; we choose those nodes with odd value to make then a circle.\n\n\n```\nclass Solution {\npublic:\n    vector<int> findRedundantConnection(vector<vector<int>>& edges) {\n        vector<int> result;\n        vector<vector<int>> graph(edges.size() + 1);\n        for (auto e:edges) {\n            graph[e[0]].push_back(e[1]);\n            graph[e[1]].push_back(e[0]);\n        }\n        vector<int> visited(edges.size() + 1, 0);\n        //start dfs from node 1\n        dfs(graph, visited, 1, 0);\n        for (int i = edges.size() - 1; i >= 0; i--) {\n            //if the visited[node] is odd, then it means the node is inside the cicle\n            if (visited[edges[i][0]]%2 && visited[edges[i][1]]%2) {\n                result = edges[i];\n                break;\n            }\n        }\n        return result;\n    }\n    //false means this node is in a circle, we want to keep the value to odd (most case would be 1)\n    //true means this node is not in a circle, we want to keep the value to 2\n    bool dfs(vector<vector<int>>& graph, vector<int>& visited, int node, int parent) {\n        if (visited[node] == 2) return true;\n        if (visited[node] == 1) {\n            // this node is the beginning node of the circle while traversing the graph, record it with 4 for the first time\n            visited[node] = 4;\n            return false;\n        }\n        visited[node] = 1;\n        for (int i = 0; i < graph[node].size(); i++) {\n            if (graph[node][i] != parent) {\n                if (!dfs(graph, visited, graph[node][i], node)) {\n                    if (visited[graph[node][i]] == 3) {//that children node graph[node][i] is the beginning of the circle\n                        continue;\n                    }\n                    //if this node value becomes 4, then mark it to 3 and let it\'s parent\n                    //node recognize that it is the beginning of a circle and continue bfs even if it returns false \n                    if (visited[node] == 4) \n                        visited[node] = 3;\n                    return false;\n                }\n            }\n        }\n        visited[node] = 2;\n        return true;\n    }\n};\n```\n\n\n\n
[]