Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.InputStreamReader;
- import java.io.InputStream;
- import java.io.*;
- import java.util.*;
- public class BerbisnisDonat{
- private static InputReader in;
- private static PrintWriter out;
- private static ArrayList<Integer>[] adj_list;
- private static HashMap<String, Integer> bobot = new HashMap<String, Integer>();
- private static ArrayList<String>[] inc_list;
- private static HashMap<String, Arraylist<Integer>> edge_list = new HashMap<>();
- private static boolean[] flag;
- private static int[] pred;
- public static void main(String[] args) throws IOException{
- in = new InputReader(System.in);
- out = new PrintWriter(System.out);
- int N = in.nextInt(); // jumlah kota atau verteks
- int M = in.nextInt(); // jumlah jalan raya atau edge
- int Q = in.nextInt(); // jumlah query atau perintah
- adj_list = (Arraylist<Integer>[]) new Arraylist[M]; // adjacency list
- inc_list = (Arraylist<String>[]) new Arraylist[N]; // incident list
- for(int i=0; i<M; i++){
- int kota_U = in.nextInt();
- int kota_V = in.nextInt();
- int bobot_jalan = in.nextInt();
- // menambahkan tetangga
- adj_list[kota_U].add(kota_V);
- adj_list[kota_V].add(kota_U);
- // menambahkan bobot
- bobot.put("e"+(i+1), bobot_jalan);
- // inisiasi array flag untuk list kota
- flag = new boolean[N];
- // inisiasi array pred untuk menyimpan kota sebelumnya
- pred = new int[N];
- // menambahkan jalan raya di incident list
- inc_list[kota_U].add("e"+(i+1));
- inc_list[kota_V].add("e"+(i+1));
- // menambahkan kota di edge list
- Arraylist<Integer> list_kota = new Arraylist<Integer>();
- list_kota.add(kota_U);
- list_kota.add(kota_V);
- edge_list.put("e"+(i+1), list_kota);
- }
- for(int j=0; j<Q; j++){
- String query = in.next();
- if(query.equals("OS")){
- String[] list_toko_buka = in.nextLine().split();
- for(int k=0; k<list_toko_buka.length; k++){
- if(pred[list_toko_buka[k]] != 0){
- DFS(list_toko_buka[k]);
- }
- }
- OS();
- }
- }
- out.close();
- }
- public static void DFS(int s){
- for(int i=0; i<flag.length; i++){
- flag[i] = false;
- }
- pred[s] = -1;
- RDFS(s);
- }
- public static void RDFS(int v){
- flag[v] = true;
- for(int tetangga : adj_list[v]){
- if(flag[tetangga] == false){
- pred[tetangga] = v;
- RDFS(tetangga);
- }
- }
- }
- public static int path(int w){
- if(pred[w] != -1){
- path(pred[w]);
- }
- return w;
- }
- public static int OS(){
- int counter = 0;
- for(int i=0; i<pred.length; i++){
- if(pred[i] != 0){
- counter++;
- }
- }
- return counter;
- }
- static class InputReader {
- // taken from https://codeforces.com/submissions/Petr
- public BufferedReader reader;
- public StringTokenizer tokenizer;
- public InputReader(InputStream stream) {
- reader = new BufferedReader(new InputStreamReader(stream), 32768);
- tokenizer = null;
- }
- public String next() {
- while (tokenizer == null || !tokenizer.hasMoreTokens()) {
- try {
- tokenizer = new StringTokenizer(reader.readLine());
- } catch (IOException e) {
- throw new RuntimeException(e);
- }
- }
- return tokenizer.nextToken();
- }
- public int nextInt() {
- return Integer.parseInt(next());
- }
- public String nextLine(){
- return reader.readLine();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement