用java实现嵌套连结算法

嵌套连结算法是一种算法，用于在有向图中查找强连通分量。以下是使用Java实现嵌套连结算法的基本步骤：

1. 定义一个有向图类，包括节点和边。
2. 创建一个栈来存储已访问的节点。
3. 对每个节点进行深度优先搜索，并将已访问的节点压入栈中。
4. 对于每个节点，记录其发现时间和低链接值，以确定其所属的强连通分量。
5. 当遇到已经访问过的节点时，将其从栈中弹出并更新其祖先的低链接值。
6. 重复步骤3-5直到所有节点都被访问。

以下是一个简单的Java实现：

import java.util.*;

public class Graph {
    private int V; // 节点数量
    private List<Integer>[] adj; // 邻接表
    private boolean[] visited; // 节点是否被访问过
    private int[] disc; // 节点的发现时间
    private int[] low; // 节点的低链接值
    private Stack<Integer> stack; // 存储已访问的节点
    private int time; // 计时器

    public Graph(int V) {
        this.V = V;
        adj = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
        visited = new boolean[V];
        disc = new int[V];
        low = new int[V];
        stack = new Stack<>();
    }

    public void addEdge(int v, int w) {
        adj[v].add(w);
    }

    public void SCC() {
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                DFS(i);
            }
        }
    }

    private void DFS(int v) {
        visited[v] = true;
        disc[v] = low[v] = ++time;
        stack.push(v);

        for (int w : adj[v]) {
            if (!visited[w]) {
                DFS(w);
                low[v] = Math.min(low[v], low[w]);
            } else if (stack.contains(w)) {
                low[v] = Math.min(low[v], disc[w]);
            }
        }

        if (low[v] == disc[v]) {
            System.out.print("SCC: ");
            while (!stack.isEmpty()) {
                int w = stack.pop();
                System.out.print(w + " ");
                if (w == v) {
                    break;
                }
            }
            System.out.println();
        }
    }
}

在上面的代码中，我们首先定义了一个有向图类，其中包括节点数量和邻接表。然后我们创建了一个栈来存储已访问的节点，并为每个节点记录了发现时间和低链接值。对于每个节点，我们进行深度优先搜索，并将已访问的节点压入栈中。在搜索过程中，我们记录了每个节点的发现时间和低链接值，并在遇到已经访问过的节点时，将其从栈中弹出并更新其祖先的低链接值。最后，我们输出每个强连通分量的节点。