Given a directed graph G that consists of (multiple of) a node connected to a segment of nodes, how would you find its SCC?

But here I propose a very simple algorithm that can solve this problem in the same time complexity ($$$O((M + N) \log N))$$$ (with M being the number of segments and N being the number of nodes).

set<int> _mark;
void dfs(int i)
{
    _mark.erase(i);
    for (auto &[a, b] : adj[i])
    {
        auto x = _mark.lower_bound(a);
        while (x != _mark.end() && *x <= b)
        {
            dfs(*x);
            x = _mark.lower_bound(a);
        }
    }
    tp.push_back(i);
}
void dfs_T(int i, int c)
{
    _mark.erase(i);
    for (auto &[a, b] : adj_[i])
    {
        auto x = _mark.lower_bound(a);
        while (x != _mark.end() && *x <= b)
        {
            dfs_T(*x, c);
            x = _mark.lower_bound(a);
        }
    }
    IDX[i] = c;
}

Why this works: dfs or dfs_T will always call on an existing node, so it'll be called n times. The time complexity is obvious from the set complexity.

Application: https://atcoder.jp/contests/arc069/submissions/78513905.

But what about the graph consisting of segments connected to segments? It probably can be solved in $$$O((M+N)\log^2(N))$$$ with the segment tree method, but doesn't apply here. I guess...

Also the problem above has a trivial transpose ($$$|M^T|=|M|$$$) of the graph. This probably makes it easier...