001package algs41;
002import stdlib.*;
003import algs13.Queue;
004/* ***********************************************************************
005 *  Compilation:  javac CC.java
006 *  Execution:    java CC filename.txt
007 *  Dependencies: Graph.java StdOut.java Queue.java
008 *  Data files:   http://algs4.cs.princeton.edu/41undirected/tinyG.txt
009 *
010 *  Compute connected components using depth first search.
011 *  Runs in O(E + V) time.
012 *
013 *  %  java CC tinyG.txt
014 *  3 components
015 *  0 1 2 3 4 5 6
016 *  7 8
017 *  9 10 11 12
018 *
019 *************************************************************************/
020
021public class CC {
022        private final boolean[] marked;   // marked[v] = has vertex v been marked?
023        private final int[] id;           // id[v] = id of connected component containing v
024        private final int[] size;         // size[id] = number of vertices in component containing v
025        private int count;                // number of connected components
026
027        public CC(Graph G) {
028                marked = new boolean[G.V()];
029                id = new int[G.V()];
030                size = new int[G.V()];
031                for (int v = 0; v < G.V(); v++) {
032                        if (!marked[v]) {
033                                dfs(G, v);
034                                count++;
035                        }
036                }
037        }
038
039        // depth first search
040        private void dfs(Graph G, int v) {
041                marked[v] = true;
042                id[v] = count;
043                size[count]++;
044                for (int w : G.adj(v)) {
045                        if (!marked[w]) {
046                                dfs(G, w);
047                        }
048                }
049        }
050
051        // id of connected component containing v
052        public int id(int v) {
053                return id[v];
054        }
055
056        // size of connected component containing v
057        public int size(int v) {
058                return size[id[v]];
059        }
060
061        // number of connected components
062        public int count() {
063                return count;
064        }
065
066        // are v and w in the same connected component?
067        public boolean areConnected(int v, int w) {
068                return id(v) == id(w);
069        }
070
071
072        // test client
073        public static void anotherTest() {
074                Graph G;
075                do {
076                        G = GraphGenerator.simple(20,40);
077                } while (new CC(G).count() != 1);
078                G.toGraphviz ("g.png");
079        }
080        public static void main(String[] args) {
081                anotherTest();
082//              args = new String [] { "10", "5" };
083//              final int V = Integer.parseInt(args[0]);
084//              final int E = Integer.parseInt(args[1]);
085//              final Graph G = GraphGenerator.simple(V, E);
086//              StdOut.println(G);
087
088                //args = new String [] { "data/tinyAG.txt" };
089                args = new String [] { "data/tinyG.txt" };
090                In in = new In(args[0]);
091                Graph G = GraphGenerator.fromIn (in);
092                StdOut.println(G);
093                G.toGraphviz ("g");
094                
095                CC cc = new CC(G);
096
097                // number of connected components
098                int M = cc.count();
099                StdOut.println(M + " components");
100
101                // compute list of vertices in each connected component
102                @SuppressWarnings("unchecked")
103                Queue<Integer>[] components = new Queue[M];
104                for (int i = 0; i < M; i++) {
105                        components[i] = new Queue<>();
106                }
107                for (int v = 0; v < G.V(); v++) {
108                        components[cc.id(v)].enqueue(v);
109                }
110
111                // print results
112                for (int i = 0; i < M; i++) {
113                        for (int v : components[i]) {
114                                StdOut.print(v + " ");
115                        }
116                        StdOut.println();
117                }
118        }
119}