Java 实现了一个分解强连通分量算法及其中遇到的两个问题

起因是帮兄弟的忙，需要完成一个强连通分量算法。好久没写过这东西了，而且当年玩儿 ACM 时用的还是 C++，现在由于各方面原因需要使用 Java。在这个过程中，遇到了两个问题：无法创建泛型数组 和 递归太深导致栈溢出，再此记录下来。

强连通分量

首先说一下强连通分量的定义：

在一个有向图中，对于它的某个子集 S，如果在 S 内任取两个顶点 u 和 v，都能找到一条从 u 到 v 的路径，那么就说 S 是强连通的。如果在 S 中加入任意其他点集合，它都不在是强连通的，那么就说 S 是原图的一个强连通分量。

一个简单的算法就是两次 dfs，具体证明以后另开文章介绍，直接贴最终代码：

class Scc {
    HashMap<Integer, ArrayList<Integer>> G, rG;
    Stack<Integer> vs;
    HashSet<Integer> used, nodes;
    
    Scc() {
        nodes = new HashSet<Integer>();
        G = new HashMap<Integer, ArrayList<Integer>>();
        rG = new HashMap<Integer, ArrayList<Integer>>();
    }
    
    void addEdge(int from, int to) {
        if (G.get(from) == null)
            G.put(from, new ArrayList<Integer>());
        if (rG.get(to) == null)
            rG.put(to, new ArrayList<Integer>());
        
        G.get(from).add(to);
        rG.get(to).add(from);
        
        nodes.add(from);
        nodes.add(to);
    }
    
    void dfs(int u) {
        used.add(u);
        ArrayList<Integer> next = G.get(u);
        if (next != null) {
            for (int i = 0; i < next.size(); i++) {
                int v = next.get(i);
                if (!used.contains(v)) {
                    dfs(v);
                }
            }
        }
        vs.push(u);
    }
    
    void rdfs(int u) {
        used.add(u);
        ArrayList<Integer> next = rG.get(u);
        if (next != null) {
            for (int i = 0; i < next.size(); i++) {
                int v = next.get(i);
                if (!used.contains(v)) {
                    rdfs(v);
                }
            }
        }
    }
    
    int solve() {
        used = new HashSet<Integer>();
        vs = new Stack<Integer>();
        
        for (int u: nodes) {
            if (!used.contains(u))
                dfs(u);
        }
        
        used.clear();
        int k = 0;
        
        while (!vs.empty()) {
            int u = vs.pop();
            if (!used.contains(u)) {
                rdfs(u); k++;
            }
        }
        
        return k;
    }
}

无法创建泛型数组

首先在写这份代码的过程中就遇到一个问题，在 C++ 中，为了方便的实现一个邻接表，通常可以直接使用 vector：

vector<int> G[maxv];

然后添加一条边从 u 到 v 的有向边时，只需要这样：

G[u].push_back(v);

简单粗暴，不需要手写一个邻接表结构，而且效率上表现的也不错，关于邻接表的细节打算后面再写一篇文章介绍。

看了上面的代码，转用 Java 写时，很自然的写出下面的代码：

ArrayList<Integer>[] G = new ArrayList<Integer>[maxv];

然后直接收到了一个错误：Cannot create a generic array of ArrayList<Integer>

表示不解，于是翻阅资料后在 stackoverflow 上找到了这份解答：
https://stackoverflow.com/questions/4549192/create-an-array-of-arrayliststring-elements

所以，你没办法创建一个泛型数组，不过文章中介绍了几种解决方案：

1. 使用 ArrayList<ArrayList<String>>
2. 去掉泛型，改为：ArrayList<Integer>[] G = new ArrayList[maxv];
3. 如果你一定要创建一个泛型数组的话，可以这样做：

public class StringArrayList extends ArrayList<String>{}

ArrayList<String> name[] = new StringArrayList[9];

而我在上面的代码中使用了 HashMap，刚好也符合邻接表的实现：

HashMap<Integer, ArrayList<Integer>> G = new HashMap<Integer, ArrayList<Integer>>();

递归太深导致爆栈

终于代码编译通过了，跑了几组数据也没问题，然而突然在某一组数据中爆炸：Exception in thread "main" java.lang.StackOverflowError

哈？第一反应是递归写矬了？后来仔细检查后认为递归没有问题，那就只有一个可能，是真的爆栈了，那么显然是 JVM 的递归栈太小了，如何调整栈的参数呢？

查找资料后有如下结论，只需要调整一下 -Xss 参数就可以了：

JDK5.0 以后每个线程堆栈大小为 1M,以前每个线程堆栈大小为 256K。在相同物理内存下,减小这个值能生成更多的线程。来自这篇文章：JVM系列三:JVM参数设置、分析

调整参数后在尝试一下：

java -Xss2M Main

这次终于可以正常运行了。