Redundant Connection

class Solution {
public:

    bool dfs(int i, int par, vector<vector<int>>& graph, vector<bool> &vis, vector<int> &cycle){
        vis[i] = 1;
        cycle.push_back(i);

        for(int a : graph[i]){
            if(!vis[a]){
                if(dfs(a, i,graph, vis, cycle)){
                    return true;
                }
            }
            else if(par!=a){
                cycle.push_back(a);
                return true;
            }
        }

        cycle.pop_back();
        return false;

    }

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

        vector<bool> vis(n, 0);
        vector<vector<int>> graph(n);

        for(auto vec : edges){
            int a = vec[0]-1, b = vec[1]-1;
            graph[a].push_back(b);
            graph[b].push_back(a);
        }

        vector<int> ans, cycle;

        dfs(0,-1 , graph, vis, cycle);

        int last = cycle[cycle.size()-1];
        int i=cycle.size()-1;

        unordered_map<int, int> mp;

        do{
            mp[cycle[i]]=1;
            i--;
        }
        while(cycle[i]!=last);

        for(auto vec : edges){
            int a = vec[0]-1, b = vec[1]-1;
            if(mp[a]==1 && mp[b]==1){
                ans = vec;
            }
        }

        return ans;
    }
};