Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.InputStreamReader;
- import java.io.IOException;
- import java.util.Iterator; import java.util.ArrayList;
- import java.util.Queue;
- /* Class Graph memiliki properti int JUMLAH_VERTEX, merupakan jumlah vertex pada graf
- *
- * Vertex pada graf dilabeli menggunakan bilangan bulat 0 sampai dengan JUMLAH_VERTEX-1.
- *
- * Adjacency List direpresentasikan menggunakan array of ArrayList. Index pada array merepresentasikan
- vertex i. ArrayList berisi bilangan-bilangan bulat, merepresentasikan vertex yang terhubung dengan
- vertex i.
- *
- *
- * Contoh: Berikut ini merupakan representasi graf dengan 5 buah vertex dan 2 connected component.
- * (3) (0) | array[0] => 1 2
- * \ / \ (4) | array[1] => 0 2
- * \ / \ | array[2] => 0 1 3
- * \/ \ | array[3] => 2
- * (2)-----(1) | array[4] =>
- */
- class Graph{
- private static int JUMLAH_VERTEX;
- private static ArrayList<Integer> adjList[];
- private static boolean[] isVisited;
- Graph(int v){
- JUMLAH_VERTEX = v;
- isVisited = new boolean[v];
- adjList = new ArrayList[v];
- for (int i=0; i<JUMLAH_VERTEX; i++) adjList[i] = new ArrayList();
- }
- void addEdge(int v, int w){
- adjList[v].add(w);
- adjList[w].add(v);
- }
- static int countConnectedComponents(){
- // implementasi program Anda di sini
- int visited = 0;
- int i = 0;
- int jumlah =0;
- while (visited<JUMLAH_VERTEX) {
- if (!isVisited[i]) {
- visited+=DFS(i);
- jumlah++;
- }
- else {
- i++;
- }
- }
- return jumlah;
- }
- static int DFS(int i) {
- int connected = 1;
- Iterator<Integer> itr = adjList[i].listIterator();
- isVisited[i]=true;
- while(itr.hasNext()){
- int x = itr.next();
- if (!isVisited[x]) {
- isVisited[x]=true;
- connected+=DFS(x);
- }
- }
- return connected;
- }
- /* Method untuk mencetak representasi adjacency list dari sebuah graf (untuk gambaran saja) */
- static void printGraph(Graph g){
- for(int i=0; i<JUMLAH_VERTEX; i++){
- Iterator<Integer> itr = adjList[i].listIterator();
- System.out.print(i+" => ");
- while(itr.hasNext()){
- System.out.print(itr.next()+" ");
- }
- System.out.println("");}}
- public static void main(String args[]) throws IOException{
- BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
- String[] in = reader.readLine().split(" ");
- int jmlVertex = Integer.parseInt(in[0]);
- int jmlEdge = Integer.parseInt(in[1]);
- Graph graf = new Graph(jmlVertex);
- //representasi matriks
- //boolean[][] adjacencyMatrix = new boolean[JUMLAH_VERTEX][JUMLAH_VERTEX];
- for(int i=0; i<jmlEdge; i++){
- in = reader.readLine().split(" ");
- graf.addEdge(Integer.parseInt(in[0]), Integer.parseInt(in[1]));
- //representasi matriks
- /*
- adjacencyMatrix[Integer.parseInt(in[0])][ Integer.parseInt(in[1])] = true;
- adjacencyMatrix[Integer.parseInt(in[1])][ Integer.parseInt(in[0])] = true;
- */
- }
- System.out.print(countConnectedComponents());
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement