Simple First Cycle/Union Find Two Solution First Connection
IntuitionThe problem asks us to find a redundant connection in a graph formed by edges. A "redundant connection" is the edge that, when added, creates a cycle.
# Intuition
The problem asks us to find a redundant connection in a graph formed by edges. A "redundant connection" is the edge that, when added, creates a cycle. We are tasked with finding the **first such edge** in the given list. Since the graph initially has no cycles, our goal is to detect the first edge that completes a cycle.
# -------------------------------------------------------- 
![Screenshot 2025-01-29 061348.png](https://assets.leetcode.com/users/images/9a8ce0ec-e27c-4c27-9150-bf92b50520bc_1738111719.5995586.png)
![Screenshot 2025-01-29 061354.png](https://assets.leetcode.com/users/images/f2f7b2f4-93f1-4c0e-9c5c-7b99c765f0cc_1738111592.6958299.png)
# --------------------------------------------------------- #


To achieve this, we maintain a representation of the graph using an adjacency list. We can then determine if adding a new edge forms a cycle by checking if there is already a path between the two nodes of that edge. If a path exists, the edge forms a cycle, and we return it.

# Approach
1. **Graph Representation**:  
   Use an `unordered_map<int, vector<int>>` to represent the graph as an adjacency list. This data structure allows us to dynamically store the connections between nodes and efficiently traverse the graph.

2. **Cycle Detection Without DFS/BFS**:  
   Instead of a standard DFS or BFS, implement a custom iterative path-checking mechanism:
   - Use a stack to simulate traversal starting from one node.
   - Use an `unordered_set` to track visited nodes during this process.
   - If the target node is found during traversal, it indicates that adding the current edge would form a cycle.

3. **Processing Edges**:  
   - Iterate through each edge in the input.
   - Before adding an edge, check if there is already a path between the two nodes using the path-checking function (`isConnected`).
   - If a path exists, return the current edge as it forms the first cycle.
   - If no path exists, add the edge to the graph by updating the adjacency list.

4. **Termination**:  
   Once we find the first edge forming a cycle, return it. Otherwise, if no cycles are detected (which won't happen based on the problem constraints), return an empty result.

# Complexity
- **Time Complexity**:  
  - For each edge, we check if there is a path between two nodes using an iterative traversal.
  - In the worst case, this traversal can visit all nodes \(O(V)\), and we repeat this for each edge \(O(E)\).
  - Hence, the overall time complexity is \(O(E+ V)\), where \(E\) is the number of edges and \(V\) is the number of nodes.

- **Space Complexity**:  
  - The adjacency list requires \(O(V + E)\) space.
  - The stack and visited set for traversal require \(O(V)\) space during path checking.
  - Therefore, the total space complexity is \(O(V + E)\).
  #  ✨✨
![Screenshot 2025-01-24 064633.png](https://assets.leetcode.com/users/images/e40c685d-6f07-4ba4-9491-c3205050e715_1738111796.9040542.png)

![Screenshot 2025-01-29 065415.png](https://assets.leetcode.com/users/images/4944d418-d820-40b0-b9d9-a899c4a39716_1738113953.8286304.png)



# Code
```C++_STACK+UNORDERMAP []
class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        unordered_map<int, vector<int>> graph;

        auto isConnected = [&](int u, int v) {
            unordered_set<int> visited;
            stack<int> stack;
            stack.push(u);

            while (!stack.empty()) {
                int node = stack.top();
                stack.pop();

                if (visited.count(node)) continue;
                visited.insert(node);

                if (node == v) return true;

                for (int neighbor : graph[node]) {
                    stack.push(neighbor);
                }
            }
            return false;
        };

        for (const auto& edge : edges) {
            int u = edge[0], v = edge[1];

            if (graph.count(u) && graph.count(v) && isConnected(u, v)) {
                return edge;
            }

            graph[u].push_back(v);
            graph[v].push_back(u);
        }

        return {};
    }
};
```
```C++_UNION_FIND []
class DisjointSet {
    vector<int> parent, depth;
public:
    DisjointSet(int n) : parent(n), depth(n) {
        depth.assign(n, 1);
        iota(parent.begin(), parent.end(), 0);
    }

    int getRoot(int x) {
        if (x == parent[x])
            return x;
        return parent[x] = getRoot(parent[x]);
    }

    bool merge(int x, int y) {
        int rootX = getRoot(x), rootY = getRoot(y);
        if (rootX == rootY)
            return false;
        if (depth[rootX] > depth[rootY])
            swap(rootX, rootY);
        parent[rootX] = rootY;
        if (depth[rootX] == depth[rootY])
            depth[rootY]++;
        return true;
    }
};

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        DisjointSet ds(n + 1);
        for (auto& edge : edges)
            if (!ds.merge(edge[0], edge[1])) return edge;
        return {};
    }
};
```
['Stack', 'Union Find', 'Graph', 'Ordered Map', 'C++']