<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<int> parent;
    int is_cycle = 0;
    void dfs(int node,vector<vector<int>> &graph,unordered_map<int,int> &ans,vector<int> &col,int par)
    {
        col[node] = 2;
        parent[node] = par;
        for(auto v : graph[node])
        {
            if(v==par)
            continue;

            if(col[v]==1)
            dfs(v,graph,ans,col,node);
            else if(col[v]==2)
            {
                int temp = node;
                while(temp!=v && !is_cycle)
                {
                    ans[temp]++;
                    temp = parent[temp];
                }
                ans[temp]++;
                is_cycle=1;
            }
        }

        col[node] = 3;
    }

    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        vector<vector<int>> graph(n+1);
        parent.assign(n+1,-1);

        int last_node = 1;
        for(auto e : edges)
        {
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
            last_node = e[0];
        }
        
        unordered_map<int,int> ans;
        vector<int> col(n+1,1);
        dfs(1,graph,ans,col,-1);

        vector<int> res(2);
        for(auto e : edges)
        {
            if(ans[e[0]] && ans[e[1]])
            {
                res[0] = e[0];
                res[1] = e[1];
            }
        }

        return res;
    }
};
14373