Tarjan 连通分量算法

#include<bits/stdc++.h>
using namespace std;

// =====================================================================================
// 一、全局变量完整说明（务必在 main 之前定义）
// const int N = 1e5 + 10;        // 最大节点数，按题目调整
// int  n, m;                     // n 节点数，m 边数
// int  dfn[N], low[N], col[N];   // dfn:时间戳 low:可回溯最前 col:所属SCC编号
// bool vis[N];                   // vis[i]=1 表示 i 当前在栈中
// int  Stack[N], top = 0;        // 手写栈，top 指向栈顶（空栈时 top=0）
// int  cnt = 0, tot = 0;         // cnt:SCC 计数器 tot:时间戳计数器
// vector<int> a[N];              // 邻接表存图
// vector<int> d[N];              // d[i] 保存第 i 个 SCC 的所有节点
// 调用方式：
//   for(int i = 1; i <= n; ++i) if(!dfn[i]) dfs(i);
// =====================================================================================

// =====================================================================================
// 函数名：get_col
// 功  能：当 Tarjan 发现 dfn[x] == low[x] 时，说明 x 是当前强连通分量(SCC)的根。
//         此时栈中从 x 到栈顶的所有节点恰好构成一个完整的 SCC。
//         本函数负责一次性弹出这些节点，并给它们统一染色（编号），
//         同时把该 SCC 的所有节点升序保存到 d[cnt] 中。
// 复杂度：均摊 O(该 SCC 的节点数)，因为每个节点只会被弹出一次。
// =====================================================================================
inline void get_col(int x){
    int y = -1;                 // y 用于临时接收栈顶节点，初值随意
    ++cnt;                      // cnt 是全局 SCC 计数器，从 1 开始编号
                                // 每找到一个 SCC 就 ++，因此新 SCC 编号为 cnt
    while(y != x){              // 循环直到把根 x 也弹出为止
        y = Stack[top--];       // Stack 是手写数组模拟的栈，top 指向栈顶
                                // 执行出栈操作：先取 Stack[top]，再 --top
        vis[y] = 0;             // vis[y] == 1 表示 y 在栈中；出栈后及时清零
                                // 防止后续再次访问到 y 时误判为仍在栈中
        col[y] = cnt;           // col[y] 记录节点 y 所属的 SCC 编号
        d[cnt].push_back(y);    // d[cnt] 是一个 vector<int>，保存该 SCC 的所有节点
    }
    sort(d[cnt].begin(), d[cnt].end()); // 题目/需求：把该 SCC 的节点按升序排序
                                        // 注意：end 必须写成 end()，否则编译错误
}

// =====================================================================================
// 函数名：dfs
// 功  能：Tarjan 主过程，对每个尚未访问的节点调用一次即可求出整张图的所有 SCC。
// 参  数：x 为当前正在访问的节点。
// 复杂度：每个节点、每条边仅访问一次，总复杂度 O(n + m)。
// 关键点：
//   1. dfn[x] 记录节点 x 的 DFS 序（时间戳）。
//   2. low[x] 记录 x 能追溯到的最早祖先的 dfn 值。
//   3. 当 dfn[x] == low[x] 时，x 是其所在 SCC 的根。
// =====================================================================================
void dfs(int x){
    dfn[x] = low[x] = ++tot;    // tot 是全局时间戳计数器，初值为 0
                                // 每次 ++tot 后赋给 dfn[x]，保证时间戳唯一且递增
    vis[x] = 1;                 // vis[x] = 1 表示 x 已入栈，防止重复入栈
    Stack[++top] = x;           // 手写栈：++top 后把 x 存入 Stack[top]
                                // 注意：Stack 数组大小需 ≥ n+10，防止越界
    // 遍历 x 的所有出边（接上文）
    for(int i = 0; i < (int)a[x].size(); i++){
        int v = a[x][i];        // v 是 x 的后继节点
        if(!dfn[v]){            // 1) v 尚未访问：树边（白色）
            dfs(v);             // 递归处理 v
            low[x] = min(low[x], low[v]); // 回溯时用 v.low 更新 x.low
        }
        else if(vis[v]){        // 2) v 已访问且仍在栈中：回边/横叉边（灰色）
            low[x] = min(low[x], dfn[v]); // 用 v.dfn 更新 x.low
            // 注意：不能写成 low[v]，否则可能把已出栈的 SCC 信息带回来
        }
        // 3) v 已访问且已出栈（黑色）：说明 v 属于更早的 SCC，直接忽略
    }

    // 回溯到根：若 dfn[x] == low[x]，则 x 是其 SCC 的根
    if(dfn[x] == low[x])        // 根节点判定条件
        get_col(x);             // 弹出栈中 x 及其以上所有节点，形成 SCC
}

// =====================================================================================
// 主函数示例：读图 + 调用 Tarjan + 输出每个 SCC
// =====================================================================================
/*
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // 1. 读入节点数 n 和边数 m
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        int u, v;
        cin >> u >> v;
        a[u].push_back(v);      // 有向图，只加单向边
    }

    // 2. 对每个尚未访问的节点启动 Tarjan
    for(int i = 1; i <= n; ++i)
        if(!dfn[i]) dfs(i);

    // 3. 输出结果示例：共 cnt 个 SCC，每个 SCC 的节点列表已升序
    cout << "共 " << cnt << " 个强连通分量\n";
    for(int i = 1; i <= cnt; ++i){
        cout << "SCC #" << i << " : ";
        for(int node : d[i]) cout << node << ' ';
        cout << '\n';
    }
    return 0;
}
*/

// =====================================================================================
// 常见坑点 & 调试技巧
// 1. Stack 数组大小必须 ≥ n+10，防止越界。
// 2. sort 必须写 d[cnt].end()，漏括号会编译错误。
// 3. vis 数组在出栈后必须置 0，否则后续会误判。
// 4. 若图不保证连通，需对每个未访问节点都 dfs(i)。
// 5. 若需要缩点建新图，可在 get_col 里顺便记录每个 SCC 的代表节点。
// 6. 若节点编号从 0 开始，请把所有循环改为 0 ~ n-1。
// =====================================================================================

#include <bits/stdc++.h>
using namespace std;
// =====================================================================================
// 一、全局变量完整说明（务必在 main 之前定义）
//const int N = 1e5 + 10; // 最大节点数
//
//int n, m; // n 节点数，m 边数
//int dfn[N], low[N], col[N]; // dfn:时间戳 low:可回溯最前 col:所属EBC编号
//bool vis[N]; // vis[i]=1 表示 i 当前在栈中
//int Stack[N], top = 0; // 手写栈，top 指向栈顶（空栈时 top=0）
//int cnt = 0, tot = 0; // cnt:EBC 计数器 tot:时间戳计数器
//vector<pair<int, int>> a[N]; // 邻接表存图（pair.first:目标节点，pair.second:边的另一端节点）
//vector<int> d[N]; // d[i] 保存第 i 个 EBC 的所有节点

// =====================================================================================
// 函数名：get_col
// 功  能：当发现 low[x] == dfn[x] 时，说明 x 是当前边双连通分量(EBC)的根。
//         此时栈中从 x 到栈顶的所有节点恰好构成一个完整的 EBC。
//         本函数负责一次性弹出这些节点，并给它们统一染色（编号），
//         同时把该 EBC 的所有节点保存到 d[cnt] 中。
// 复杂度：均摊 O(该 EBC 的节点数)，因为每个节点只会被弹出一次。
// =====================================================================================
inline void get_col(int x)
{
    int y = -1;
    ++cnt; // cnt 是全局 EBC 计数器，每找到一个 EBC 就 ++，因此新 EBC 编号为 cnt
    while (x != y)
    {
        y = Stack[top--]; // Stack 是手写数组模拟的栈，top 指向栈顶；执行出栈操作：先取 Stack[top]，再 --top
        vis[y] = 0; // vis[y]=1 表示 y 在栈中；出栈后及时清零，防止后续再次访问到 y 时误判为仍在栈中
        col[y] = cnt; // col[y] 记录节点 y 所属的 EBC 编号
        d[cnt].push_back(y); // d[cnt] 是一个 vector<int>，保存该 EBC 的所有节点
    }
}

// =====================================================================================
// 函数名：dfs
// 功  能：边双连通分量主过程，对每个尚未访问的节点调用一次即可求出整张图的所有 EBC。
// 参  数：x 为当前正在访问的节点，fa 为 x 的父节点（用于避免回头边）。
// 复杂度：每个节点、每条边仅访问一次，总复杂度 O(n + m)。
// 关键点：
//   1. dfn[x] 记录节点 x 的 DFS 序（时间戳）。
//   2. low[x] 记录 x 能追溯到的最早祖先的 dfn 值。
//   3. 当 low[x] == dfn[x] 时，x 是其所在 EBC 的根。
// =====================================================================================
void dfs(int x, int fa)
{
    dfn[x] = low[x] = ++tot; // tot 是全局时间戳计数器，初值为 0；每次 ++tot 后赋给 dfn[x]，保证时间戳唯一且递增
    vis[x] = 1; // vis[x] = 1 表示 x 已入栈，防止重复入栈
    Stack[++top] = x; // 手写栈：++top 后把 x 存入 Stack[top]；注意：Stack 数组大小需 ≥ n+10，防止越界

    for (int i = 0; i < a[x].size(); ++i)
    {
        if (a[x][i].second == fa) continue; // 跳过父边，避免回头

        int v = a[x][i].first; // v 是 x 的直接后继节点

        if (!dfn[v]) // 情况1：v 尚未访问过（dfn[v] == 0），此时 (x,v) 是一条树边（DFS 树中的边）
        {
            dfs(v, a[x][i].second); // 递归访问 v
            low[x] = min(low[x], low[v]); // 回溯时用 v 的 low 更新 x 的 low

            if (low[v] >= dfn[x]) // 如果 low[v] >= dfn[x]，则 (x,v) 是割边（桥），需要新建 EBC
                get_col(x); // 弹出栈中 x 及其以上所有节点，形成新的 EBC
        }
        else if (vis[v]) // 情况2：v 已访问过且仍在栈中（vis[v] == 1），此时 (x,v) 是一条非树边（回边或横叉边）
            low[x] = min(low[x], dfn[v]); // 用 v 的 dfn 更新 low[x]
    }
}

// =====================================================================================
// 主函数示例：读图 + 调用边双连通分量算法 + 输出每个 EBC
// =====================================================================================
/*
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 1. 读入节点数 n 和边数 m
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v;
        a[u].push_back({v, u}); // 有向图，只加单向边；pair.first:目标节点，pair.second:边的另一端节点
        a[v].push_back({u, v});
    }

    // 2. 对每个尚未访问的节点启动 dfs
    for (int i = 1; i <= n; ++i)
        if (!dfn[i])
            dfs(i, -1); // -1 表示没有父节点

    // 3. 输出结果示例：共 cnt 个边双连通分量，每个 EBC 的节点列表
    cout << "共 " << cnt << " 个边双连通分量\n";
    for (int i = 1; i <= cnt; ++i)
    {
        cout << "EBC #" << i << " : ";
        for (int node : d[i])
            cout << node << ' ';
        cout << '\n';
    }

    return 0;
}
*/

// =====================================================================================
// 常见坑点 & 调试技巧
// 1. Stack 数组大小必须 ≥ n+10，防止越界。
// 2. 若图不保证连通，需对每个未访问节点都 dfs(i, -1)。
// 3. 若需要缩点建新图，可在 get_col 里顺便记录每个 EBC 的代表节点。
// 4. 若节点编号从 0 开始，请把所有循环改为 0 ~ n-1。
// 5. 注意边的存储方式：a[u].push_back({v, u}) 和 a[v].push_back({u, v})。
// =====================================================================================

#include <bits/stdc++.h>
using namespace std;

// =====================================================================================
// 一、全局变量完整说明（务必在 main 之前定义）
//const int N = 1e5 + 10; // 最大节点数
//
//int n, m; // n 节点数，m 边数
//int dfn[N], low[N], col[N]; // dfn:时间戳 low:可回溯最前 col:所属VBC编号
//bool vis[N]; // vis[i]=1 表示 i 当前在栈中
//int Stack[N], top = 0; // 手写栈，top 指向栈顶（空栈时 top=0）
//int cnt = 0, tot = 0; // cnt:VBC 计数器 tot:时间戳计数器
//vector<int> a[N]; // 邻接表存图
//vector<int> d[N]; // d[i] 保存第 i 个 VBC 的所有节点

// =====================================================================================
// 函数名：get_col
// 功  能：当发现当前节点 x 是割点且其子节点 v 的 low[v] >= dfn[x] 时，
//         或者 x 是 DFS 树的根且有多个子节点时，说明找到了一个点双连通分量（VBC）。
//         本函数负责一次性弹出这些节点，并给它们统一染色（编号），
//         同时把该 VBC 的所有节点保存到 d[cnt] 中。
// 复杂度：均摊 O(该 VBC 的节点数)，因为每个节点只会被弹出一次。
// =====================================================================================
inline void get_col(int x)
{
    int y = -1;
    ++cnt; // cnt 是全局 VBC 计数器，每找到一个 VBC 就 ++，因此新 VBC 编号为 cnt
    while (x != y)
    {
        y = Stack[top--]; // Stack 是手写数组模拟的栈，top 指向栈顶；执行出栈操作：先取 Stack[top]，再 --top
        vis[y] = 0; // vis[y]=1 表示 y 在栈中；出栈后及时清零，防止后续再次访问到 y 时误判为仍在栈中
        col[y] = cnt; // col[y] 记录节点 y 所属的 VBC 编号
        d[cnt].push_back(y); // d[cnt] 是一个 vector<int>，保存该 VBC 的所有节点
    }
}

// =====================================================================================
// 函数名：dfs
// 功  能：点双连通分量主过程，对每个尚未访问的节点调用一次即可求出整张图的所有 VBC。
// 参  数：x 为当前正在访问的节点。
// 复杂度：每个节点、每条边仅访问一次，总复杂度 O(n + m)。
// 关键点：
//   1. dfn[x] 记录节点 x 的 DFS 序（时间戳）。
//   2. low[x] 记录 x 能追溯到的最早祖先的 dfn 值。
//   3. 当 low[v] >= dfn[x] 时（v 是 x 的子节点），x 是割点，需要新建 VBC。
// =====================================================================================
void dfs(int x)
{
    dfn[x] = low[x] = ++tot; // tot 是全局时间戳计数器，初值为 0；每次 ++tot 后赋给 dfn[x]，保证时间戳唯一且递增
    vis[x] = 1; // vis[x] = 1 表示 x 已入栈，防止重复入栈
    Stack[++top] = x; // 手写栈：++top 后把 x 存入 Stack[top]；注意：Stack 数组大小需 ≥ n+10，防止越界

    if (!a[x].size()) // 如果 x 是叶子节点（没有子节点）
    {
        get_col(x); // 直接弹出 x 形成单节点 VBC
        return;
    }

    int child = 0; // 记录 x 的子节点数量
    for (int i = 0; i < a[x].size(); ++i)
    {
        int v = a[x][i];
        if (!dfn[v]) // v 尚未访问过（dfn[v] == 0），此时 (x,v) 是一条树边（DFS 树中的边）
        {
            ++child;
            dfs(v); // 递归访问 v
            low[x] = min(low[x], low[v]); // 回溯时用 v 的 low 更新 x 的 low

            if (low[v] >= dfn[x]) // 如果 low[v] >= dfn[x]，则 x 是割点，需要新建 VBC
            {
                get_col(x); // 弹出栈中 x 及其以上所有节点，形成新的 VBC
                d[cnt].push_back(x); // x 本身也属于该 VBC
            }
        }
        else if (vis[v]) // v 已访问过且仍在栈中（vis[v] == 1），此时 (x,v) 是一条非树边（回边或横叉边）
            low[x] = min(low[x], dfn[v]); // 用 v 的 dfn 更新 low[x]
    }

    if (child == 1 && x == Stack[1]) // 如果 x 是 DFS 树的根且只有一个子节点，特殊处理
        get_col(x); // 弹出 x 形成单节点 VBC
}

// =====================================================================================
// 主函数示例：读图 + 调用点双连通分量算法 + 输出每个 VBC
// =====================================================================================
/*
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 1. 读入节点数 n 和边数 m
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v;
        a[u].push_back(v); // 无向图，加双向边
        a[v].push_back(u);
    }

    // 2. 对每个尚未访问的节点启动 dfs
    for (int i = 1; i <= n; ++i)
        if (!dfn[i])
            dfs(i);

    // 3. 输出结果示例：共 cnt 个点双连通分量，每个 VBC 的节点列表
    cout << "共 " << cnt << " 个点双连通分量\n";
    for (int i = 1; i <= cnt; ++i)
    {
        cout << "VBC #" << i << " : ";
        for (int node : d[i])
            cout << node << ' ';
        cout << '\n';
    }

    return 0;
}
*/

// =====================================================================================
// 常见坑点 & 调试技巧
// 1. Stack 数组大小必须 ≥ n+10，防止越界。
// 2. 若图不保证连通，需对每个未访问节点都 dfs(i)。
// 3. 若需要缩点建新图，可在 get_col 里顺便记录每个 VBC 的代表节点。
// 4. 若节点编号从 0 开始，请把所有循环改为 0 ~ n-1。
// 5. 注意边的存储方式：无向图需要加双向边。
// =====================================================================================