C++ (4 approaches, DFS -> BFS -> UNION Find -> Union Find with rank) with Comments
Know more about interview questions : https://github.com/MAZHARMIK/Interview_DS_Algo\n\n//Approach-1 (DFS)\nclass Solution {\npublic:\n    bool dfs(map<int, vec
Know more about interview questions : https://github.com/MAZHARMIK/Interview_DS_Algo\n```\n//Approach-1 (DFS)\nclass Solution {\npublic:\n    bool dfs(map<int, vector<int>>& mp, int start, int end, vector<bool>& visited) {\n        visited[start] = true;\n        if(start == end)\n            return true;\n        \n        for(int &x : mp[start]) {\n            if(!visited[x] && dfs(mp, x, end, visited)) {\n                return true;\n            }\n        }\n        return false;\n    }\n    \n    vector<int> findRedundantConnection(vector<vector<int>>& edges) {\n        map<int, vector<int>> mp;\n        \n        int n = edges.size();\n        vector<bool> visited(n+1, false);\n        \n        for(int i = 0; i<n; i++) {\n            int u = edges[i][0];\n            int v = edges[i][1];\n            \n            fill(begin(visited), end(visited), false);\n            \n            //if u and v are already in graph, then we check\n            //if this current edge connects them again ?\n            //If yes, this edge is unwanted (redundant)\n            if(mp.find(u) != mp.end() && mp.find(v) != mp.end()\n              && dfs(mp, u, v, visited))\n                return edges[i];\n            \n            //Else, add them to graph\n            mp[u].push_back(v);\n            mp[v].push_back(u);\n        }\n        \n        return {};\n    }\n};\n```\n\n```\n//Approach-2 (BFS)\nclass Solution {\npublic:\n    int n;\n    bool bfs(map<int, vector<int>>& mp, int start, int end) {\n        vector<bool> visited(n+1, false);\n        queue<int> que;\n        que.push(start);\n        \n        while(!que.empty()) {\n            int curr = que.front();\n            que.pop();\n            visited[curr] = true;\n            if(curr == end)\n                return true;\n            \n            for(int &x : mp[curr]) {\n                if(!visited[x]) {\n                    que.push(x);\n                }\n            }\n        }\n        return false;\n    }\n    vector<int> findRedundantConnection(vector<vector<int>>& edges) {\n        map<int, vector<int>> mp;\n        n = edges.size();\n        \n        for(int i = 0; i<n; i++) {\n            int u = edges[i][0];\n            int v = edges[i][1];\n            \n            //if u and v are already in graph, then we check\n            //if this current edge connects them again ?\n            //If yes, this edge is unwanted (redundant)\n            if(mp.find(u) != mp.end() && mp.find(v) != mp.end() && bfs(mp, u, v))\n                return edges[i];\n            \n            //Else add them to graph\n            mp[u].push_back(v);\n            mp[v].push_back(u);\n        }\n        \n        return {};\n    }\n};\n```\n\n```\n//Approach-3 (Union Find with Path compression)\nclass Solution {\npublic:\n    int find(int x, vector<int>& parent) {\n        if(parent[x] != x)\n            return parent[x] = find(parent[x], parent); //Path compression\n        \n        return parent[x];\n    }\n    \n    void Union(int u, int v, vector<int>& parent) {\n        parent[u] = v;\n    }\n    \n    vector<int> findRedundantConnection(vector<vector<int>>& edges) {\n        int n = edges.size();\n        vector<int> parent(n+1);\n        for(int i = 1; i<=n; i++)\n            parent[i] = i;\n        for(int i = 0; i<n; i++) {\n            int u = edges[i][0];\n            int v = edges[i][1];\n            \n            int set_u = find(u, parent);\n            int set_v = find(v, parent);\n            \n            if(set_u == set_v) {\n                //means they were already connected before\n                //So, this edge is redundant\n                return edges[i];\n            }\n            \n            //Else, bring them in one subset\n            Union(set_u, set_v, parent);\n        }\n        return {};\n    }\n};\n```\n\n```\n//Approach-4 (Union Find with Rank and Path Compression)\nclass Solution {\npublic:\n    int find(int x, vector<vector<int>>& parent) {\n        if(parent[x][0] != x)\n            return parent[x][0] = find(parent[x][0], parent); //Path Compression\n        \n        return parent[x][0];\n    }\n    \n    void Union(int u, int v, vector<vector<int>>& parent) {\n\t\t//Union by Rank\n        //put node of lower rank under node of higher rank\n        if(parent[u][1] < parent[v][1]) {\n            parent[u][0] = v;\n        } else if(parent[u][1] > parent[v][1]) {\n            parent[v][0] = u;\n        } else {\n            parent[u][0] = v;\n            parent[u][1]++; //increase rank of v\n        }\n    }\n    \n    vector<int> findRedundantConnection(vector<vector<int>>& edges) {\n        int n = edges.size();\n        vector<vector<int>> parent(n+1, vector<int>(2, 0));\n        //parent[i][0] = parent of i\n        //parent[i][1] = rank of i\n        \n        for(int i = 1; i<=n; i++) {\n            parent[i][0] = i;\n            parent[i][1] = 0; //initially rank = 0\n        }\n        \n        for(int i = 0; i<n; i++) {\n            int u = edges[i][0];\n            int v = edges[i][1];\n            \n            int set_u = find(u, parent);\n            int set_v = find(v, parent);\n            \n            if(set_u == set_v) {\n                //means they were already connected before\n                //So, this edge is redundant\n                return edges[i];\n            }\n            \n            //Else, bring them in one subset\n            Union(set_u, set_v, parent);\n        }\n        return {};\n    }\n};\n```\n
[]