C++ Union Find algorithm with explanation
@user1128l asked for Union Find altorithm. This is the example code (Accepted, but only beats ~20%).\n\nPlease note that this is a "Bridge-Finding" problem, and
@user1128l asked for Union Find altorithm. This is the example code (Accepted, but only beats ~20%).\n\nPlease note that this is a "Bridge-Finding" problem, and the best way is **Tarjan algorithm**.\n\n```\nclass Solution {\nprivate:\n    vector<vector<int>> adjMap; // for our graph\n    vector<int> id; // for our Union Find algorithm\nprivate:\n    // create this graph\'s adjacency map\n    void createAdjacencyMap(vector<vector<int>>& connections, int n){\n        adjMap=vector<vector<int>>(n, vector<int>());\n        for(const auto& v2 : connections){\n            adjMap[v2[0]].push_back(v2[1]);\n            adjMap[v2[1]].push_back(v2[0]);\n        }\n    }\n    // returns the group id of node p with path compression algorithm\n    int find(int p){\n        while(p!=id[p]){\n            id[p]=id[id[p]];\n            p=id[p];\n        }\n        return p;\n    }\n    // unite node p and q, making them in the same group\n    // so that find(p) and find(q) will return the same group id in the future\n    void unite(int p, int q){\n        int pConn=find(p), qConn=find(q);\n        if(pConn!=qConn)\n            id[qConn]=pConn;\n    }\n    // unite the parent chain: {from, parent[from], ..., to}\n    // so that {from, parent[from], ..., to} will all be in the same group\n    void uniteCycle(int from, int to, const vector<int>& parent){\n        while(from!=to){\n            unite(from, parent[from]);\n            from=parent[from];\n        }\n    }\n    // DFS visit the node, uniting them if they are in the same cycle\n    void dfsVisit(int node, vector<int>& visited, vector<int>& parent){\n        visited[node]=1; // set the node as "open/being visited"\n        for(int adj : adjMap[node]){\n            // we need to deal with the situation where adj was visited;\n            // so we should filter out this situation (adj is node\'s parent) first\n            if(adj==parent[node]) continue;\n            // if adj is being visited, then adj must be node\'s ancestor            \n            if(visited[adj]==1){\n                // if node\'s group id is different than adj\'s group id\n                // we unite them\n                if(find(node)!=find(adj))\n                    uniteCycle(node, adj, parent);\n            }else if(visited[adj]==0){\n                parent[adj]=node;\n                dfsVisit(adj, visited, parent);\n            }\n            // note: if visited[adj]==2, it means that adj was closed\n            // in that case, adj can NOT be node\'s ancestor.\n        }\n        visited[node]=2; // set the node as "fully visited"\n    }\n    // mark the same group id to all the nodes in the same cycle\n    void reduce(){\n        // DFS with the info of visited and parent\n        vector<int> visited(id.size(), 0);\n        vector<int> parent(id.size(), -1);\n        for(int i=0;i<(int)id.size();i++){\n            if(!visited[i])\n                dfsVisit(i, visited, parent);\n        }\n    }\npublic:\n    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {\n        // id for union find: at first, each node\'s group id is itself\n        id=vector<int>(n,0);\n        for(int i=1;i<n;i++)\n            id[i]=i;\n        // create adjacent list\n        createAdjacencyMap(connections,n);\n        // reduce cycles with union find\n        reduce();\n        // check connections: push the connection into result\n        //  if the two nodes belong to different connecting components\n        vector<vector<int>> res;\n        for(vector<int>& twoNodes : connections){\n            if(find(twoNodes[0])!=find(twoNodes[1]))\n                res.push_back(twoNodes);\n        }\n        return res;\n    }\n};\n```
[]