C++ | BFS + two-pointer approach  | Time & Space O(E+V) | Explanation
\nThis is my BFS solution. \nAnd the passed submission detail is here\nhttps://leetcode.com/submissions/detail/704217278/\nIt\'s already pass this submit. \nEve
\nThis is my BFS solution. \nAnd the passed submission detail is here\nhttps://leetcode.com/submissions/detail/704217278/\nIt\'s already pass this submit. \nEven I pass all current testcase but maybe it is not totally correct. \n\n# Idea \n(1) We can use BFS to find a spanning tree in this graph. And all the edge in this answer must show in this spanning tree.\n(2) There is no any cycle subgraph of this graph can contain the edge of the answer. \n\nSo my final idea for this algorithm is that try to find all possible cycle subgraph when every time you \nevaluate the edge should belong to this BFS spanning tree or not. \nWhen everytime you find an cycle, then all edge in this cycle must not belong the answer.\n\n\nSecond information is that we can try to use observe BFS algorithm more and what it should look like in a graph. \nWe can find out something new in BFS here and let me share it to you here.\nWhen you do a BFS algorithm in the graph, then the BFS tree could like the folloiwng tree\n```\n       o     --- level 0\n    /     \\\n   o       o   --- level 1\n  / \\     / \\\n o   o   o   o   --- level 2\n/ \\ / \\ / \\ / \\\n ....\n \no o o .... o o o  --- level n\n```  \neach level mean different distance from root to the vertex \nand no edge can broke triangle inequality here.\n\nThe travelling style of BFS algorithm will do \nUse current level 0  to build next level 1\nUse current level 1  to build next level 2\n...\nUse current level n-1  to build next level n\n\nAnd when algorithm use current level i to build next level i+1, the algorithm can find out\n(1)\nsome edge should not belong to BFS spanning and the such edge must make a cycle if you add this edge.\n\n(2) The such edge (u,v) only happen in \n   (a) u,v are both in level i-1  \n   (b) u in level i-1, v in level i but there is a u\' in level i-1 and edge (u\',i) have already in this BFS spanning tree. \n   (c) u in level i-1 but v in level i-2 \n\nSo in the source code \nI use `currS.find(v) != currS.end() || nextS.find(v) != nextS.end()` to find out the above case(a) and case(b)\nAnd we don\'t need to do anything for case(c). \n\nWhen we use `currS.find(v) != currS.end() || nextS.find(v) != nextS.end()` to find out some edge can make cycle subgraph, \nthen we can travel all edge in this cycle and make sure the edge in cycle will not belong to answer. \nWe use two-pointer to solve this problem.  In the idea of algorithm, it easy to understand. \nBut in the implmentation this is the most complicated part here in this code. \n\n```C++\n\tif(currS.find(v) != currS.end() || nextS.find(v) != nextS.end()) {                    \n\t\twhile(vmp[u]!=vmp[v]) {\n\t\t\tif(edges[vmp[v]].level > edges[vmp[u]].level) {                        \n\t\t\t\tedges[vmp[v]].selected = false;\n\t\t\t\tvmp[v] = vmp[edges[vmp[v]].u];//up one edge of v\n\t\t\t} else if (edges[vmp[v]].level < edges[vmp[u]].level) {\n\t\t\t\tedges[vmp[u]].selected = false;\n\t\t\t\tvmp[u] = vmp[edges[vmp[u]].u];//up one edge of u\n\t\t\t} else {\n\t\t\t\tedges[vmp[v]].selected = false;\n\t\t\t\tedges[vmp[u]].selected = false;\n\t\t\t\tvmp[v] = vmp[edges[vmp[v]].u];\n\t\t\t\tvmp[u] = vmp[edges[vmp[u]].u];\n\t\t\t}\n\t\t}\n\t}\n```\n\n\n\n\n# Source Code \n\n```C++\nclass Solution {\npublic:\n\n    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {\n        struct edge{int u; int v;int level; bool selected;};//edge from u to v \n        vector<vector<int>> ans;\n        unordered_map<int,unordered_set<int>> emp;\n        for(auto &e:connections) {\n            emp[e[0]].insert(e[1]);\n            emp[e[1]].insert(e[0]);\n        }\n        vector<edge> edges;\n        unordered_map<int,int> vmp; //map from vertex to index of edges\n        unordered_set<int> s;//travelled set\n        unordered_set<int> realCurrS, realNextS, &currS = realCurrS, &nextS = realNextS;\n        queue<int> realCurrQ, realNextQ, &currQ = realCurrQ, &nextQ = realNextQ;\n        \n        currQ.push(0);\n        currS.insert(0);\n        \n        edges.push_back(edge{-1, 0, -1, true});\n        vmp[0] = 0;\n        int level = 0;\n        \n        while(!currQ.empty()) {\n            int u = currQ.front();\n            currQ.pop();\n            for(auto &v : emp[u]) {\n\n                if(currS.find(v) != currS.end() || nextS.find(v) != nextS.end()) {                    \n                    while(vmp[u]!=vmp[v]) {\n                        if(edges[vmp[v]].level > edges[vmp[u]].level) {                        \n                            edges[vmp[v]].selected = false;\n                            vmp[v] = vmp[edges[vmp[v]].u];//up one edge of v\n                        } else if (edges[vmp[v]].level < edges[vmp[u]].level) {\n                            edges[vmp[u]].selected = false;\n                            vmp[u] = vmp[edges[vmp[u]].u];//up one edge of u\n                        } else {\n                            edges[vmp[v]].selected = false;\n                            edges[vmp[u]].selected = false;\n                            vmp[v] = vmp[edges[vmp[v]].u];\n                            vmp[u] = vmp[edges[vmp[u]].u];\n                        }\n                    }\n                } else if(s.find(v) == s.end()) {\n                    edge added_edge = edge{u,v,level,true};\n                    edges.push_back(added_edge);\n                    vmp[v] = edges.size() - 1;\n                    nextS.insert(v);\n                    nextQ.push(v);\n                }\n            }\n            if(currQ.empty()) {\n                for(auto &v:currS) s.insert(v);\n                currS = nextS;\n                nextS = unordered_set<int>();                \n                swap(currQ,nextQ);\n                ++level;\n            }\n        }\n        \n\n        for(auto& e: edges) {\n            if(e.selected == true && e.u >=0) {\n                vector<int>ae;\n                ae.push_back(e.u);\n                ae.push_back(e.v);\n                ans.push_back(ae);\n            }\n        }\n        return ans;\n    }\n};\n```\n\n\n# Complexity Analysis \nTime complexity O(V+E)\nSpace complexity O(V+E)
['Breadth-First Search', 'C']