Advertisement
Guest User

Untitled

a guest
Dec 12th, 2018
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.11 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.io.IOException;
  4. import java.util.Iterator; import java.util.ArrayList;
  5. import java.util.Queue;
  6.  
  7. /* Class Graph memiliki properti int JUMLAH_VERTEX, merupakan jumlah vertex pada graf
  8. *
  9. * Vertex pada graf dilabeli menggunakan bilangan bulat 0 sampai dengan JUMLAH_VERTEX-1.
  10. *
  11. * Adjacency List direpresentasikan menggunakan array of ArrayList. Index pada array merepresentasikan
  12. vertex i. ArrayList berisi bilangan-bilangan bulat, merepresentasikan vertex yang terhubung dengan
  13. vertex i.
  14. *
  15. *
  16. * Contoh: Berikut ini merupakan representasi graf dengan 5 buah vertex dan 2 connected component.
  17. * (3) (0) | array[0] => 1 2
  18. * \ / \ (4) | array[1] => 0 2
  19. * \ / \ | array[2] => 0 1 3
  20. * \/ \ | array[3] => 2
  21. * (2)-----(1) | array[4] =>
  22. */
  23. class Graph{
  24. private static int JUMLAH_VERTEX;
  25. private static ArrayList<Integer> adjList[];
  26. private static boolean[] isVisited;
  27. Graph(int v){
  28. JUMLAH_VERTEX = v;
  29. isVisited = new boolean[v];
  30. adjList = new ArrayList[v];
  31. for (int i=0; i<JUMLAH_VERTEX; i++) adjList[i] = new ArrayList();
  32. }
  33. void addEdge(int v, int w){
  34. adjList[v].add(w);
  35. adjList[w].add(v);
  36. }
  37. static int countConnectedComponents(){
  38. // implementasi program Anda di sini
  39. int visited = 0;
  40. int i = 0;
  41. int jumlah =0;
  42.  
  43. while (visited<JUMLAH_VERTEX) {
  44. if (!isVisited[i]) {
  45. visited+=DFS(i);
  46. jumlah++;
  47. }
  48. else {
  49. i++;
  50. }
  51. }
  52.  
  53. return jumlah;
  54. }
  55.  
  56. static int DFS(int i) {
  57. int connected = 1;
  58. Iterator<Integer> itr = adjList[i].listIterator();
  59. isVisited[i]=true;
  60. while(itr.hasNext()){
  61. int x = itr.next();
  62. if (!isVisited[x]) {
  63. isVisited[x]=true;
  64. connected+=DFS(x);
  65. }
  66. }
  67. return connected;
  68. }
  69.  
  70. /* Method untuk mencetak representasi adjacency list dari sebuah graf (untuk gambaran saja) */
  71. static void printGraph(Graph g){
  72. for(int i=0; i<JUMLAH_VERTEX; i++){
  73. Iterator<Integer> itr = adjList[i].listIterator();
  74. System.out.print(i+" => ");
  75. while(itr.hasNext()){
  76. System.out.print(itr.next()+" ");
  77. }
  78. System.out.println("");}}
  79. public static void main(String args[]) throws IOException{
  80. BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  81. String[] in = reader.readLine().split(" ");
  82. int jmlVertex = Integer.parseInt(in[0]);
  83. int jmlEdge = Integer.parseInt(in[1]);
  84. Graph graf = new Graph(jmlVertex);
  85. //representasi matriks
  86. //boolean[][] adjacencyMatrix = new boolean[JUMLAH_VERTEX][JUMLAH_VERTEX];
  87. for(int i=0; i<jmlEdge; i++){
  88. in = reader.readLine().split(" ");
  89. graf.addEdge(Integer.parseInt(in[0]), Integer.parseInt(in[1]));
  90. //representasi matriks
  91. /*
  92. adjacencyMatrix[Integer.parseInt(in[0])][ Integer.parseInt(in[1])] = true;
  93. adjacencyMatrix[Integer.parseInt(in[1])][ Integer.parseInt(in[0])] = true;
  94. */
  95. }
  96. System.out.print(countConnectedComponents());
  97. }
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement