We can solve it in O(sqrt(n) " log(n)), log in base 10.

You're right; I only saw that my solution would work for N <= 10^18, while this one wouldn't.

But asymptotically the sqrt() one is better, whoops.

Ur welcome

About the articulation point statement: it was an example. Anyway, being more precise, if the articulation point belongs to the sequence p₁, ..., p_k, v then there is no problem. Also, if this situation happens, it is guaranteed that it will happen exactly once. The articulation point will necessarily appear as the root of any other cycles. Consider this example:

Suppose that your DFS starts at 3 and you get the sequence 3, 1, 4, 5. As you can see, the fact that 1 is labeled the same as the rest of vertices is not problematic. However, it must be excluded from the other cycle in order to avoid joining two disjoint simple cycles.

About the cost:

Let's break down the editorial's code and comment the pieces.

void dfs(int u, int pu, int d) {
    dep[u] = d;
    color[u] = 1;
    p[u] = pu;
    for (int v: g[u]) {
        if (v == pu)
            continue;
        if (p[v] == -1)
            dfs(v, u, d + 1);
        else if (color[v] == 1)
            be.push_back({u, v});
    }
    color[u] = 2;
}

This is a classic DFS. We visit all vertices exactly once, so this is linear. So, our verdict is

pp = p;
k = be.size();
for (int i = 0; i < k; i++) {
    int x = be[i].first;
    vector<int> path;
    while (dep[x] > dep[be[i].second]) {
        path.push_back(x);
        if (index[x] == -1)
            index[x] = i;
        else
            unite(i, index[x]); // DSU
        x = p[x];
    }
    for (auto j: path)
        p[j] = be[i].second;
}

This one is tricky. Let's first pretend that this part does not exist:

    for (auto j: path)
        p[j] = be[i].second;

If this last loop was not present the code would run in . Supposing that our graph consists of a single connected component, we see that only a linear amount of edges won't be back-edges in our DFS tree. So if we have a quadratic amount of edges (e.g: complete graph) we will execute the cycle reconstruction phase a quadratic amount of times, this is bad!

However, let's think about the last loop:

    for (auto j: path)
        p[j] = be[i].second;

This part of the code guarantees us that we will never traverse the same path twice. Let's consider the sequence of vertices u, v, s, t such that there is a back-edge (u, t), par(t) = s, par(s) = v, and par(v) = u. This magic loops ensures that par(t) = par(s) = par(v) = u after processing the path. Great! Note that the length of the longest path in any DFS tree is at most n - 1. These two facts (we never revisit + length of longest path) makes the code run in .

And now let's consider the last part of the code:

vector<int> sizes(k);
for (int i =  0; i < k; i++)
    sizes[leader(i)]++;

set<int> result;
for (int i = 0; i < be.size(); i++)
    if (sizes[i] == 1) {
        result.insert(e[{be[i]}]);
        int x = be[i].first;
        while (x != be[i].second) {
            result.insert(e[{x, pp[x]}]);
            x = pp[x];
        }
    }

This is tricky again, as you may think something like "hey, this code can potentially run in because any back edge can potentially trigger the inner loop!". Actually, it does not. Note that we only process sets such that they have exactly one simple cycle. The direct implication of this fact is that these sets will surely be disjoint (if they were not, any edge would belong to more than one cycle, which is precisely what we are avoiding!). Given that we have at most n vertices, this code is also !