用邻接矩阵表示的有向无环图判断是否有强连通分量

用邻接矩阵表示的有向无环图（DAG），要判断是否有强连通分量，可以采用Kosaraju’s Strongly Connected Components (SCCs)算法。这个算法分为两个步骤：

1. **Topological Sorting**:
- 对于DAG，可以先进行一次前序遍历或拓扑排序，这将得到一个线性的顺序，其中所有指向另一个节点的边都出现在被指向前的节点之后。
- 如果在排序过程中无法形成一个完全有序的序列，说明图中存在循环。

2. **DFS查找SCCs**:
- 使用深度优先搜索（DFS），同时维护一个栈和一个集合，用于记录当前正在搜索的路径以及发现的SCC。
- 从第一个未访问过的节点开始，如果进入一个新的未访问过的SCC，就将其添加到集合中并更新栈顶元素。
- 当回溯到一个已经访问过的节点时，表示找到了一个完整的SCC，此时从栈顶弹出的所有节点构成一个SCC。

以下是伪代码示例：

function kosaraju_dfs(v, visited, stack, scc_set):
    visited[v] = true
    stack.push(v)
    
    while stack not empty:
        u = stack.top()
        stack.pop()
        
        for neighbor in adj[u]:
            if visited[neighbor] == false:
               kosaraju_dfs(neighbor, visited, stack, scc_set)
                
        if u not in scc_set:
            scc_set.add(u)

function hasStronglyConnectedComponents(adj_matrix):
    n = size_of(adj_matrix)
    visited = [false] * n
    stack = []
    scc_set = set()

    topological_sort = perform_topological_sort(adj_matrix)

    # 反向搜索寻找SCCs
    for node in reversed(topological_sort):
        if visited[node] == false:
            kosaraju_dfs(node, visited, stack, scc_set)

    # 如果scc_set大小等于n，说明图是强连通的
    return len(scc_set) == n