用DFS但不进行顶点标号了，在如果无圈则在回溯时记录点对可达性，例如：

V0 -> V1 -> V2 -> V3 -> V4 -> V5 -> V6 -> V7
            |           ^
            |(V2到V8)   |(V10到V4)
            V8 -> V9 -> V10

那么在第一支路：V0,V1,V2,V3,V4,V5,V6,V7，记录２３４５６７之间的可达性，０１２之间的可达性，以及０１２与３４５６７的可达性．
第二支路：V0,V1,V2,V8,V9,V10,V4,V5,V6,V7，记录V8,V9,V10与V4的可达性，（邻接矩阵存储，同时可以记录V8,V9,V10与V5,V6,V7的可达性），在记录V0,V1,V2与V8,V9,V10的可达性．

有圈时仍用并查集．
不知这样可否？

• 您这个并查集能用在有向图么？ 而且能仔细分析一下复杂度么？ (419) sunmoonstar_love 2005-09-02 13:29:03
  • Re:您这个并查集能用在有向图么？ 而且能仔细分析一下复杂度么？ (136) qingshuang100 2005-09-02 13:37:41
• Re:我来辩解一下，呵呵 (419) xreborner 2005-09-02 14:50:42
• 错了错了，才没有这么简单。你做一下就知道了，最坏情况时间复杂度很大的。 (0) xreborner 2005-09-02 14:51:46