连通分量.md

//使用深度优先搜索找出图中所有的连通分量
public class CC {
    private boolean[] marked;
    private int[] id;
    private int count;
    public CC(Graph G) {
        final int V = G.V();
        marked = new boolean[V];

        for (int v = 0; v < V; v++) {
            if (!marked[v]) {
                dfs(G, v);
                count++;
            }
        }
    }

    private void dfs(Graph G, int v) {
        marked[v] = true;
        id[v] = count;
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                dfs(G, w);
            }
        }
    }

    public boolean connected(int v, int w) {
        return id[v] == id[w];
    }

    public int id(int v) {
        return id[v];
    }

    public int count() {
        return count;
    }
}

// 无向图，使用邻接表
public class Graph {
    // 点的个数
    private final int V;
    // 边的个数
    private int E;
    // 邻接表
    private Map<Integer, List<Integer>> adj;

    public Graph(int V) {
        this.V = V;
        this.E = 0;
        adj = new HashMap<>();
        for (int v = 0; v < V; v++) {
            // 邻接表初始化
            List<Integer> bag = new LinkedList<>();
            adj.put(v, bag);
        }
    }

    public int V() {
        return V;
    }

    public int E() {
        return E;
    }

    // 增加一条 v->w 的边（因为是无向图，当然也要 w->v）
    public void addEdge(int v, int w) {
        List<Integer> bag = adj.get(v);
        bag.add(w);

        List<Integer> rbag = adj.get(w);
        rbag.add(v);
        // 边的个数更新
        E++;
    }

    // 节点 v 的邻接表
    public List<Integer> adj(int v) {
        return adj.get(v);
    }

}