UnionFind is good vs DFS+ bitset for cycle||beats 100%
IntuitionUse UnionFind to solve in quick.
2nd approach uses DFS+ bitset for vertices on cycle.Approach
Define the UnionFind class with rank optimization
In find
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Use UnionFind to solve in quick.
2nd approach uses DFS+ bitset for vertices on cycle.
# Approach
<!-- Describe your approach to solving the problem. -->
1. Define the UnionFind class with rank optimization
2. In `findRedundantConnection(vector<vector<int>>& edges)` let `n=|edges|`
3. Declare the Unionfind object `G(n+1)`
4. Procced a single loop `if (!G.Union(e[0], e[1])) return e` for `e in edges`
5. If the whole loop is though, return `{}`, but according to LC's description it will never reach.
> Given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added.


# UnionFind makes some quesitions easier
the usual Union Find class with members `root`, `rank`, `Find`, `Union`, `connected`! The very crucial fact is that **every vertex in a connected component shares a common root, i.e. x is connected to y** $\iff$ Find(x)==Find(y) $\iff$ root[x]==root[y]

Some problems can be solved by used UnionFind
[2658. Maximum Number of Fish in a Grid](https://leetcode.com/problems/maximum-number-of-fish-in-a-grid/solutions/6337415/ez-dfsc-beats-100-by-anwendeng-nd07/)
[959. Regions Cut By Slashes](https://leetcode.com/problems/regions-cut-by-slashes/solutions/5614770/unionfind-dfs-euler-theorem-v-e-f-2-beats-100/)
[1971. Find if Path Exists in Graph](https://leetcode.com/problems/find-if-path-exists-in-graph/solutions/5052126/union-find-is-good-vs-dfs-vs-bfs-193ms-beats-99-93/)
[Please turn English subtitles if necessary]
[https://youtu.be/B1GQlUN08lk?si=DpfxrPBWc-t5eSPi](https://youtu.be/B1GQlUN08lk?si=DpfxrPBWc-t5eSPi)
```
class UnionFind { // usual UnionFind class
    vector<int> root, rank;
public:
    UnionFind(int n) : root(n), rank(n) {
        rank.assign(n, 1);
        iota(root.begin(), root.end(), 0);
    }

    int Find(int x) {//Path compression
        if (x == root[x])
            return x;
        else
            return root[x] = Find(root[x]);
    }

    bool Union(int x, int y) {//Union by rank with connecting info
        int rX = Find(x), rY = Find(y);
        //they have same root, already in same component
        if (rX == rY)
            return 0;// does not affect the components
        if (rank[rX] > rank[rY])
            swap(rX, rY);
        root[rX] = rY;
        if (rank[rX] == rank[rY])
            rank[rY]++;
        return 1;// connect 2 disjoint components
    }
};
```
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$O((V+E)\alpha(V))$ where $\alpha(.)$ is the inverse Ackermann function which growths very slowly.
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$O(V)$
# Code||C++ 0ms beats 100%
```cpp []
class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        const int n=edges.size();
        UnionFind G(n+1);
        for(auto& e: edges)
            if (!G.Union(e[0], e[1])) return e;
        return {};
    }
};
```
# DFS + bitset for cycle|0ms
```
class Solution {
public:
    bitset<1001> viz;
    vector<vector<short>> adj;
    vector<int> parent;
    int found = -1;

    void dfs(int i) {
        viz[i] = 1;
        for (int j : adj[i]) {
            if (!viz[j]) {
                parent[j] = i;
                dfs(j);
            } else if (j != parent[i] && found == -1) {
                found = j;
                parent[j] = i;
            }
        }
    }

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

        for (auto& e : edges) {
            short u = e[0], v = e[1];
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        dfs(edges[0][0]);
        //    cout<<found<<endl;

        bitset<1001> cycle = 0;
        int j = found;
        do {
            cycle[j] = 1;
            j = parent[j];
        } while (j != found);

        for (int i = n - 1; i >= 0; i--) {
            int u = edges[i][0], v = edges[i][1];
            if (cycle[u] && cycle[v])
                return edges[i];
        }
        return {};
    }
};
```
# Relationship to Minimal Spanning Tree
It's to remove the edge with the maximal edge index which makes a cycle; in other words, the remaining edges build a spanning tree.

If putting the edge index as the edge weight, it is to find the mininimal spanning tree; ie. the spanning tree with minimal summation of weights. There are several kinds of algorithms dealing with. One is Prim's algorithm which is very similar to Dijkstra's Algorithm finding shortest path; the other using Union-Find is called Krusal's Algorithm.

The 1st solution can be reguarded as a special case for Krusal's algorithm; it doesn't need to sort the edges, the rest is very similar  to.

LC has few questions on this topic, can ref.
[1584. Min Cost to Connect All Points](https://leetcode.com/problems/min-cost-to-connect-all-points/solutions/4046658/c-prim-s-algorithm-vs-kruskal-s-algorithm-beats-96-09/)
[1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
](https://leetcode.com/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/solutions/3930534/c-kruskal-s-algorithm-beats-95-26-math/) 


['Depth-First Search', 'Union Find', 'Graph', 'C++']