布尔矩阵幂次计算问题的图论解法分析

题目理解

给定一个 $K \times K$ 的布尔矩阵，其中：

• 主对角线元素全为 $1$
• 另有 $M$ 个非对角元素为 $1$
• 需要计算该矩阵的 $2006$ 次幂，统计结果中 $1$ 的个数

解题方法

核心思路

1. 图论建模：将布尔矩阵视为有向图的邻接矩阵
2. 强连通分量：使用 Tarjan 算法找出图中的强连通分量(SCC)
3. 分量缩点：将每个 SCC 缩为一个超级节点
4. 可达性计算：在缩点后的DAG上计算可达性关系

算法实现

#include <iostream>
#include <cstring>
using namespace std;

const int maxn = 1010;
const int maxm = 10010;

struct Node {
    int be, ne;
    Node(int b = 0, int n = -1) : be(b), ne(n) {}
};

class Tarjan {
    // Tarjan算法实现
    // 包括:
    // - 初始化图结构
    // - DFS遍历计算dfn和low
    // - 识别强连通分量
    // - 缩点构建新图
};

class DP {
    // 动态规划实现
    // 包括:
    // - 初始化缩点后的图
    // - 计算各分量的可达性
    // - 统计最终结果
};

int main() {
    Tarjan tj;
    DP dp;
    int n, m, a, b;
    
    while (cin >> n >> m) {
        tj.init(n);
        while (m--) {
            cin >> a >> b;
            tj.add(a + 1, b + 1); // 转换为1-based索引
        }
        tj.solve(dp); // 执行Tarjan算法并计算最终结果
    }
    return 0;
}