Advertisement
Guest User

Untitled

a guest
Dec 6th, 2019
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.73 KB | None | 0 0
  1. import java.io.InputStreamReader;
  2. import java.io.InputStream;
  3. import java.io.*;
  4. import java.util.*;
  5.  
  6. public class BerbisnisDonat{
  7. private static InputReader in;
  8. private static PrintWriter out;
  9. private static ArrayList<Integer>[] adj_list;
  10. private static HashMap<String, Integer> bobot = new HashMap<String, Integer>();
  11. private static ArrayList<String>[] inc_list;
  12. private static HashMap<String, Arraylist<Integer>> edge_list = new HashMap<>();
  13. private static boolean[] flag;
  14. private static int[] pred;
  15.  
  16. public static void main(String[] args) throws IOException{
  17. in = new InputReader(System.in);
  18. out = new PrintWriter(System.out);
  19.  
  20. int N = in.nextInt(); // jumlah kota atau verteks
  21. int M = in.nextInt(); // jumlah jalan raya atau edge
  22. int Q = in.nextInt(); // jumlah query atau perintah
  23.  
  24. adj_list = (Arraylist<Integer>[]) new Arraylist[M]; // adjacency list
  25. inc_list = (Arraylist<String>[]) new Arraylist[N]; // incident list
  26.  
  27. for(int i=0; i<M; i++){
  28. int kota_U = in.nextInt();
  29. int kota_V = in.nextInt();
  30. int bobot_jalan = in.nextInt();
  31.  
  32. // menambahkan tetangga
  33. adj_list[kota_U].add(kota_V);
  34. adj_list[kota_V].add(kota_U);
  35.  
  36. // menambahkan bobot
  37. bobot.put("e"+(i+1), bobot_jalan);
  38.  
  39. // inisiasi array flag untuk list kota
  40. flag = new boolean[N];
  41.  
  42. // inisiasi array pred untuk menyimpan kota sebelumnya
  43. pred = new int[N];
  44.  
  45. // menambahkan jalan raya di incident list
  46. inc_list[kota_U].add("e"+(i+1));
  47. inc_list[kota_V].add("e"+(i+1));
  48.  
  49. // menambahkan kota di edge list
  50. Arraylist<Integer> list_kota = new Arraylist<Integer>();
  51. list_kota.add(kota_U);
  52. list_kota.add(kota_V);
  53. edge_list.put("e"+(i+1), list_kota);
  54. }
  55.  
  56. for(int j=0; j<Q; j++){
  57. String query = in.next();
  58. if(query.equals("OS")){
  59. String[] list_toko_buka = in.nextLine().split();
  60. for(int k=0; k<list_toko_buka.length; k++){
  61. if(pred[list_toko_buka[k]] != 0){
  62. DFS(list_toko_buka[k]);
  63. }
  64. }
  65. OS();
  66. }
  67. }
  68.  
  69. out.close();
  70. }
  71.  
  72. public static void DFS(int s){
  73. for(int i=0; i<flag.length; i++){
  74. flag[i] = false;
  75. }
  76. pred[s] = -1;
  77. RDFS(s);
  78. }
  79.  
  80. public static void RDFS(int v){
  81. flag[v] = true;
  82. for(int tetangga : adj_list[v]){
  83. if(flag[tetangga] == false){
  84. pred[tetangga] = v;
  85. RDFS(tetangga);
  86. }
  87. }
  88. }
  89.  
  90. public static int path(int w){
  91. if(pred[w] != -1){
  92. path(pred[w]);
  93. }
  94. return w;
  95. }
  96.  
  97. public static int OS(){
  98. int counter = 0;
  99. for(int i=0; i<pred.length; i++){
  100. if(pred[i] != 0){
  101. counter++;
  102. }
  103. }
  104. return counter;
  105. }
  106.  
  107. static class InputReader {
  108. // taken from https://codeforces.com/submissions/Petr
  109. public BufferedReader reader;
  110. public StringTokenizer tokenizer;
  111.  
  112. public InputReader(InputStream stream) {
  113. reader = new BufferedReader(new InputStreamReader(stream), 32768);
  114. tokenizer = null;
  115. }
  116.  
  117. public String next() {
  118. while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  119. try {
  120. tokenizer = new StringTokenizer(reader.readLine());
  121. } catch (IOException e) {
  122. throw new RuntimeException(e);
  123. }
  124. }
  125. return tokenizer.nextToken();
  126. }
  127.  
  128. public int nextInt() {
  129. return Integer.parseInt(next());
  130. }
  131.  
  132. public String nextLine(){
  133. return reader.readLine();
  134. }
  135. }
  136. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement