brief iterative C++ code took me forever to implement
I don\'t know you guys but I have a hygiene habit to always implement things in an iterative way(though sometimes not optimal). So I didn\'t hesitate it to choo
I don\'t know you guys but I have a hygiene habit to always implement things in an iterative way(though sometimes not optimal). So I didn\'t hesitate it to choose to write a stack when I first try to implement it. But things get complicated and concepts are mistaken during this process, several things I found confusing in my attempt:\n1. How to determine whether the node you wanna put to stack is the current node\'s parent?\n\n    This one is easy and should be a common skill when you try to write dfs with path history: maintain a `parent` map from the current node to its father in the dfs tree.\n2. How to go back to the node after all the subtree of this node has completed update(the update of low, if you know a bit of Tarjan algo, it\'s the lowest index among all the nodes you can traverse to through the dfs starting with current node)?\n\n    It is also simple, in the recursion method it is self-explanatory, as the stack frame of current traversal will persist even when you are traversing the subtree. But in common iterative dfs code you can read online, whether it is about tree or graph, they always discard the current node after pushing all its subtree to the stack. The simple way to mimic the recursive method is: just don\'t pop it, hold until you meet it again in the stack, it means all its subtree has been traversed, then you update the `low` of current node.\n\n3. How to deal with the nodes that were pushed to stack but already been traversed by the previous path(like the 1 in the diagram if you choose to traverse 2 first)?\n    \n    The answer is to leave it there, but do not propagate it anymore. The handling can be taken over by the snippet used to deal with the previous problem, as in the previous thing we also do not propagate the node again, but calculate the `low`. Here we do not need to calculate the `low` again, but for simplicity I did not rule them apart.\n\n```\n                                   X\n                                   X\n                                   X\n                            XX     X   XX\n                           XX      X    XXX\n                          XX              XXX\n                        XXX                 XXXX\n                                               XXX\n                   XXXXXX                        X   XXX\n                       XX                           XX  X\n                      XX                            X   XX\n                     XX        XXXXXXXXXXXXXXXX     X   XX\n                   XXXXXX                           XX XX\n                                                     XXX\n               XX\n              XX\n             X\n  XXXXXXXXX\nXXX       X\n         XX\n      XXXX\n     XXXXXXXXX\n             X\n            XX\n         XXXX\n    XXXXXX\n\n```\n\nHere is the code.\n\n```\nclass Solution\n{\npublic:\n    vector<vector<int>> criticalConnections(int n, vector<vector<int>> &connections)\n    {\n        unordered_map<int, vector<int>> adj;\n        for (auto &vec : connections)\n        {\n            adj[vec[0]].push_back(vec[1]);\n            adj[vec[1]].push_back(vec[0]);\n        }\n\n        vector<int> low(n, INT_MAX);\n        vector<int> par(n, -1);\n        stack<int> buf;\n        buf.push(0);\n        int timeStamp = 0;\n\n        while (buf.size())\n        {\n            auto cur = buf.top();\n            if (low[cur] != INT_MAX)\n            {\n                buf.pop();\n                for (auto j : adj[cur])\n                {\n                    if (j != par[cur])\n                        low[cur] = min(low[cur], low[j]);\n                }\n                continue;\n            }\n            low[cur] = timeStamp++;\n            for (auto j : adj[cur])\n            {\n                if (low[j] == INT_MAX && j != par[cur])\n                {\n                    buf.push(j);\n                    par[j] = cur;\n                }\n            }\n        }\n        vector<vector<int>> results;\n        copy_if(connections.begin(), connections.end(), back_inserter(results), [&low](vector<int> &v) -> bool { return low[v[0]] != low[v[1]]; });\n        return results;\n    }\n\n};\nstatic int x = []() { std::ios::sync_with_stdio(false); cin.tie(NULL); return 0; }();\n\n```
['C', 'Iterator']