/*************************************************************************
 *  Kompilacja:  javac CC.java
 *  Zależności: Graph.java 
 *
 *  Wyznacza spójne składowe przez wyszukiwanie w głąb.
 *  Złożoność O(E + V).
 *
 *************************************************************************/

public class CC {
    private boolean[] marked;   // marked[v] = czy oznaczono wierzchołek v?
    private int[] id;           // id[v] = identyfikator spójnej składowej obejmującej v
    private int[] size;         // size[v] = liczba wierzchołków w składowej obejmującej v
    private int count;          // Liczba spójnych składowych

    public CC(Graph G) {
        marked = new boolean[G.V()];
        id = new int[G.V()];
        size = new int[G.V()];
        for (int v = 0; v < G.V(); v++) {
            if (!marked[v]) {
                dfs(G, v);
                count++;
            }
        }
    }

    // Wyszukiwanie w głąb
    private void dfs(Graph G, int v) {
        marked[v] = true;
        id[v] = count;
        size[v]++;
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                dfs(G, w);
            }
        }
    }

    // Identyfikator spójnej składowej obejmującej v
    public int id(int v) {
        return id[v];
    }

    // Rozmiar spójnej składowej obejmującej v
    public int size(int v) {
        return size[id[v]];
    }

    // Liczba spójnych składowych
    public int count() {
        return count;
    }

    // Czy v i w znajdują się w tej samej spójnej składowej?
    public boolean areConnected(int v, int w) {
        return id(v) == id(w);
    }

    // Klient testowy
    public static void main(String[] args) {
        int V = Integer.parseInt(args[0]);
        int E = Integer.parseInt(args[1]);
        Graph G = new Graph(V, E);
        StdOut.println(G);
        CC cc = new CC(G);

        StdOut.println("Liczba spojnych skladowych = " + cc.count());
        for (int v = 0; v < G.V(); v++) {
            StdOut.println(v + ": " + cc.id(v));
        }
    }


}
