题解：最大半连通子图问题

一、题目背景

给定一个有向图 (G=(V, E))，定义了半连通图、导出子图和半连通子图的概念。要求找出图 (G) 的最大半连通子图包含的节点数 (K) ，以及不同的最大半连通子图的数目 (C) （输出 (C) 对给定数 (X) 的余数）。

二、解题思路

本题先通过Tarjan算法求出有向图的强连通分量，然后对强连通分量进行缩点，构建新图。在新图上使用动态规划的方法来求解最大半连通子图的节点数和数量。

具体步骤如下：
1. 定义图的存储结构，包括原始图邻接表 h[N]、缩点后图邻接表 hs[N]、时间戳数组 dfn[N]、追溯数组 low[N]、栈数组 stk[N] 及栈顶指针 top、节点是否在栈中的标记数组 in_stk[N]、节点所属强连通分量编号数组 id[N]、强连通分量数量 scc_cnt、每个强连通分量的大小数组 scc_size[N]、动态规划数组 f[N]（记录以每个强连通分量为起点的最大半连通子图节点数）和 g[N]（记录以每个强连通分量为起点的最大半连通子图的数量）。
2. 编写添加边的函数 add，用于构建邻接表。
3. 实现Tarjan算法函数 tarjan，用于找出图中的强连通分量：
- 更新当前节点的 dfn 和 low 值，并将节点入栈，标记在栈中。
- 遍历当前节点的邻接边，对于未访问的节点，递归调用 tarjan 并更新 low 值；对于已访问且在栈中的节点，更新 low 值。
- 若当前节点的 dfn 和 low 值相等，则表示找到了一个强连通分量，将栈中节点弹出，标记不在栈中，并记录所属强连通分量编号和大小。
4. 在 main 函数中：
- 初始化邻接表，读取图的节点数 n、边数 m 和取模值 mod。
- 读取每条边，构建原始图的邻接表。
- 对每个未访问的节点调用 tarjan 算法，找出所有强连通分量。
- 使用哈希集合 S 去除缩点后图中重复的边，构建缩点后的图的邻接表。
- 从后往前遍历每个强连通分量，进行动态规划：
- 若 f[i] 未初始化，则初始化为当前强连通分量的大小 scc_size[i]，g[i] 初始化为 1。
- 遍历当前强连通分量的出边，根据动态规划转移方程更新 f 和 g 数组。
- 遍历所有强连通分量，找出最大的 f[i] 作为最大半连通子图的节点数 maxf，并统计 f[i] 等于 maxf 时的 g[i] 之和作为最大半连通子图的数量 sum（取模）。
- 输出最大半连通子图的节点数和数量。

三、代码逐段分析

（一）头文件和全局变量

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_set>

using namespace std;

typedef long long LL;

const int N = 100010, M = 2000010;

int n, m, mod;
int h[N], hs[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, scc_size[N];
int f[N], g[N];

1. 头文件：
   • #include <cstdio>：用于标准输入输出函数，如 scanf 和 printf。
   • #include <cstring>：用于字符串操作和内存初始化函数，如 memset。
   • #include <iostream>：提供C++风格的输入输出流，如 cin 和 cout。
   • #include <algorithm>：包含一些常用的算法函数。
   • #include <unordered_set>：用于哈希集合操作。
   • using namespace std;：使用标准命名空间，以便直接使用标准库中的函数和类型。
2. 类型定义：typedef long long LL; 定义 LL 为 long long 类型，方便后续使用。
3. 常量定义：
   • const int N = 100010, M = 2000010;：定义节点的最大数量和边的最大数量。
4. 变量定义：
   • int n, m, mod;：分别表示图的节点数、边数和取模值。
   • int h[N], hs[N], e[M], ne[M], idx;：h[N] 是原始图邻接表头指针数组，hs[N] 是缩点后图邻接表头指针数组，e[M] 存储边的终点，ne[M] 存储下一条边的指针，idx 用于边的编号。
   • int dfn[N], low[N], timestamp;：dfn[N] 记录节点首次访问的时间戳，low[N] 记录节点或其子孙能追溯到的最早时间戳，timestamp 是时间戳计数器。
   • int stk[N], top;：stk[N] 是栈数组，top 是栈顶指针。
   • bool in_stk[N];：标记每个节点是否在栈中。
   • int id[N], scc_cnt, scc_size[N];：id[N] 记录节点所属强连通分量编号，scc_cnt 是强连通分量数量，scc_size[N] 存储每个强连通分量的大小。
   • int f[N], g[N];：f[N] 记录以每个强连通分量为起点的最大半连通子图节点数，g[N] 记录以每个强连通分量为起点的最大半连通子图的数量。

（二）添加边函数

void add(int h[], int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

该函数用于向邻接表中添加一条边，参数 h[] 表示邻接表头指针数组，a 为起点，b 为终点。通过更新邻接表数组，将边的信息存储起来。

（三）Tarjan算法函数

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[ ++ top] = u, in_stk[u] = true;

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u])
    {
        ++ scc_cnt;
        int y;
        do {
            y = stk[top -- ];
            in_stk[y] = false;
            id[y] = scc_cnt;
            scc_size[scc_cnt] ++ ;
        } while (y != u);
    }
}

1. 初始化当前节点的 dfn 和 low 值为当前时间戳，将节点入栈并标记在栈中。
2. 遍历当前节点的邻接边：
   • 若邻接节点未访问，递归调用 tarjan 函数，并更新当前节点的 low 值为当前 low 值和邻接节点 low 值的较小值。
   • 若邻接节点已访问且在栈中，更新当前节点的 low 值为当前 low 值和邻接节点 dfn 值的较小值。
3. 若当前节点的 dfn 和 low 值相等，说明找到了一个强连通分量：
   • 强连通分量数量加 (1)。
   • 从栈中弹出节点，标记不在栈中，记录所属强连通分量编号，增加对应强连通分量的大小。

（四）main 函数

int main()
{
    memset(h, -1, sizeof h);
    memset(hs, -1, sizeof hs);

    scanf("%d%d%d", &n, &m, &mod);
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(h, a, b);
    }

    for (int i = 1; i <= n; i ++ )
        if (!dfn[i])
            tarjan(i);

    unordered_set<LL> S;    // (u, v) -> u * 1000000 + v
    for (int i = 1; i <= n; i ++ )
        for (int j = h[i]; ~j; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            LL hash = a * 1000000ll + b;
            if (a != b &&!S.count(hash))
            {
                add(hs, a, b);
                S.insert(hash);
            }
        }

    for (int i = scc_cnt; i; i -- )
    {
        if (!f[i])
        {
            f[i] = scc_size[i];
            g[i] = 1;
        }
        for (int j = hs[i]; ~j; j = ne[j])
        {
            int k = e[j];
            if (f[k] < f[i] + scc_size[k])
            {
                f[k] = f[i] + scc_size[k];
                g[k] = g[i];
            }
            else if (f[k] == f[i] + scc_size[k])
                g[k] = (g[k] + g[i]) % mod;
        }
    }

    int maxf = 0, sum = 0;
    for (int i = 1; i <= scc_cnt; i ++ )
        if (f[i] > maxf)
        {
            maxf = f[i];
            sum = g[i];
        }
        else if (f[i] == maxf) sum = (sum + g[i]) % mod;

    printf("%d\n", maxf);
    printf("%d\n", sum);

    return 0;
}

1. 初始化原始图和缩点后图的邻接表。
2. 读取图的节点数 n、边数 m 和取模值 mod，读取每条边，构建原始图的邻接表。
3. 对每个未访问的节点调用 tarjan 算法，找出所有强连通分量。
4. 使用哈希集合 S 构建缩点后的图的邻接表，去除重复边。
5. 从后往前遍历每个强连通分量，进行动态规划：
   • 若 f[i] 未初始化，初始化 f[i] 为当前强连通分量的大小 scc_size[i]，g[i] 为 1。
   • 遍历当前强连通分量的出边，若 f[k] 小于 f[i] + scc_size[k]，更新 f[k] 和 g[k]；若 f[k] 等于 f[i] + scc_size[k]，更新 g[k]（取模）。
6. 遍历所有强连通分量，找出最大的 f[i] 作为最大半连通子图的节点数 maxf，并统计 f[i] 等于 maxf 时的 g[i] 之和作为最大半连通子图的数量 sum（取模）。
7. 输出最大半连通子图的节点数和数量。
8. 程序结束。

四、时间复杂度和空间复杂度分析

（一）时间复杂度

1. 建图：读取 (m) 条边构建原始图邻接表，时间复杂度为 (O(m))。
2. Tarjan算法：每个节点最多被访问一次，每条边最多被遍历一次，时间复杂度为 (O(n + m))。
3. 缩点建图：遍历 (m) 条边构建缩点后的图邻接表，时间复杂度为 (O(m))，使用哈希集合去重，平均时间复杂度为 (O(1))，总时间复杂度仍为 (O(m))。
4. 动态规划：遍历每个强连通分量和其出边，时间复杂度为 (O(scc_cnt + m’))，其中 (scc_cnt) 是强连通分量数量，(m’) 是缩点后图的边数，(scc_cnt\leq n)，(m’\leq m)。
5. 统计结果：遍历 (scc_cnt) 个强连通分量统计结果，时间复杂度为 (O(scc_cnt))。
   总体时间复杂度为 (O(n + m))。

（二）空间复杂度

1. 邻接表：存储原始图和缩点后图的边信息，空间复杂度为 (O(m))。
2. 其他数组：时间戳数组 dfn[N]、追溯数组 low[N]、栈数组 stk[N]、节点是否在栈中的标记数组 in_stk[N]、节点所属强连通分量编号数组 id[N]、强连通分量数量 scc_cnt、每个强连通分量的大小数组 scc_size[N]、动态规划数组 f[N] 和 g[N]，空间复杂度均为 (O(n))。
3. 哈希集合：存储缩点后图的边，空间复杂度为 (O(m))。
   总体空间复杂度为 (O(n + m))。

希望这份题解能帮助你理解这道题的解题思路和代码实现。如果有任何疑问，欢迎随时提问。