<p>In this problem, a tree is an <strong>undirected graph</strong> that is connected and has no cycles.</p>

<p>You are given a graph that started as a tree with <code>n</code> nodes labeled from <code>1</code> to <code>n</code>, with one additional edge added. The added edge has two <strong>different</strong> vertices chosen from <code>1</code> to <code>n</code>, and was not an edge that already existed. The graph is represented as an array <code>edges</code> of length <code>n</code> where <code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> indicates that there is an edge between nodes <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code> in the graph.</p>

<p>Return <em>an edge that can be removed so that the resulting graph is a tree of </em><code>n</code><em> nodes</em>. If there are multiple answers, return the answer that occurs last in the input.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/02/reduntant1-1-graph.jpg" style="width: 222px; height: 222px;" />
<pre>
<strong>Input:</strong> edges = [[1,2],[1,3],[2,3]]
<strong>Output:</strong> [2,3]
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/02/reduntant1-2-graph.jpg" style="width: 382px; height: 222px;" />
<pre>
<strong>Input:</strong> edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
<strong>Output:</strong> [1,4]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == edges.length</code></li>
	<li><code>3 &lt;= n &lt;= 1000</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>1 &lt;= a<sub>i</sub> &lt; b<sub>i</sub> &lt;= edges.length</code></li>
	<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>
	<li>There are no repeated edges.</li>
	<li>The given graph is connected.</li>
</ul>

class Solution {

    
public:
    vector<vector<int>> graph;
    
    vector<bool> done;
    vector<int> path;
    unordered_set<string> cycle;

    string getKey (int curr, int prev) {

        int small, large;

        if (curr < prev) {
            small = curr;
            large = prev;
        } else {
            small = prev;
            large = curr;
        }

        return to_string(small) + to_string(large);
    }

    void add_cycle (int start) {

        int curr = start;

        for (int i= path.size() -1; i>=0 ; i--) {

            int prev = path[i];
            string key = getKey(curr, prev);
            cycle.insert(key);

            if (prev == start) 
                break;
            
            curr = prev;
        }
    }

    bool find_cycle (int curr, int p) {

        if(done[curr]) {
            
            add_cycle(curr);
            return true;
        }

        done[curr] = true;
        path.push_back(curr);

        for (int i : graph[curr]) {

            if (i == p)
                continue;

            if (find_cycle(i, curr))
                return true;
        }

        done[curr] = false;
        path.pop_back();

        return false;
    }

    void build_graph (int n, vector<vector<int>>& edges) {

        graph = vector<vector<int>> (n);

        for (auto vec: edges) {
            graph[vec[0]].push_back(vec[1]);
            graph[vec[1]].push_back(vec[0]);
        }
    }

    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        
        int n = edges.size();

        if (n < 3)
            return {};

        build_graph(n+1, edges);

        done = vector<bool>(n+1, false);

        find_cycle(1, -1);

        int i;

        for (i = edges.size() - 1; i >=0; i--) {

            string key = getKey(edges[i][0], edges[i][1]);

            if (cycle.find(key) != cycle.end()) 
                break;
        }

        return edges[i];

    }
};
15281