684. Redundant Connection

📝 Problem Details

• Title: 684. Redundant Connection
• Link: https://leetcode.com/problems/redundant-connection/
• Difficulty: Medium
• Tags/Categories: Graphs DFS

tree: undirected graph that is connected and has no cycles input integer n representing the number of nodes in a graph (labeled from 1 to n) input array edges

💭What Were My Initial Thoughts?

- we are given a graph that was initially a tree but now has one extra edge
- a tree has exaclty n-1 edges for n nodes, so this graph now has `n` edges
- the one extra edge introduces one cycle
- the goal is to find the edge in the cycle that appears last in the input list

- the graph must remain connected after removing the extra edge
- the problem is essentially finding a cycle in an undirected graph

🤔What Did I Struggle With?

- not familiar enough with implementing DSU to use to solve this problem

💡 Explanation of Solution

- construct adjacency list
	- since the input consists of n edges and n nodes, we can dynamically construct the adjacency list
	- each edge [u,v] is bidirectional since its undirected

- perform dfs to detect a cycle
	- check for cycles before adding an edge to the graph
	- if addding an edge forms a back edge (node is visited in the same DFS path), we have found a cycle
	- the last edge that completes the cycle should be returned 

⌛ Complexity Analysis

Time Complexity: O(V+E)
Space Complexity: O(V+E)

💻 Implementation of Solution

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();  // Since the graph has n edges, it must have n nodes
        vector<vector<int>> adjList(n + 1); // Use 1-based indexing
 
        for (const auto& edge : edges) {
            int u = edge[0], v = edge[1];
 
            // Reset visited for each edge check
            vector<int> visited(n + 1, 0);
 
            // If a cycle is found, return the current edge
            if (!adjList[u].empty() && !adjList[v].empty() && dfs(u, v, adjList, visited)) {
                return edge;
            }
 
            // Otherwise, add edge to adjacency list
            adjList[u].push_back(v);
            adjList[v].push_back(u);
        }
 
        return {};
    }
 
private:
    bool dfs(int node, int target, vector<vector<int>>& adjList, vector<int>& visited) {
        if (node == target) return true; // Cycle found
        visited[node] = 1;
 
        for (int neighbor : adjList[node]) {
            if (!visited[neighbor]) {
                if (dfs(neighbor, target, adjList, visited)) return true;
            }
        }
 
        return false;
    }
};