import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class GraphKota {

    // Adjacency list: nama kota -> daftar kota yang bersisian.
    private final Map<String, List<String>> tetangga = new LinkedHashMap<>();

    public static void main(String[] args) {
        GraphKota graph = new GraphKota();
        graph.tambahSisi("Jakarta", "Bandung");
        graph.tambahSisi("Jakarta", "Semarang");
        graph.tambahSisi("Bandung", "Yogyakarta");
        graph.tambahSisi("Semarang", "Yogyakarta");
        graph.tambahSisi("Semarang", "Surabaya");
        graph.tambahSisi("Yogyakarta", "Surabaya");

        System.out.println("=== Adjacency list (graph tak berarah) ===");
        graph.cetakAdjacencyList();

        System.out.println();
        System.out.println("=== BFS mulai dari Jakarta ===");
        System.out.println("Urutan kunjungan: " + graph.bfs("Jakarta"));
    }

    void tambahSisi(String kotaA, String kotaB) {
        tetangga.computeIfAbsent(kotaA, k -> new ArrayList<>()).add(kotaB);
        tetangga.computeIfAbsent(kotaB, k -> new ArrayList<>()).add(kotaA);
    }

    String bfs(String mulai) {
        List<String> urutan = new ArrayList<>();
        Deque<String> antrean = new ArrayDeque<>();
        Map<String, Boolean> dikunjungi = new LinkedHashMap<>();
        for (String kota : tetangga.keySet()) {
            dikunjungi.put(kota, false);
        }

        dikunjungi.put(mulai, true);
        antrean.offer(mulai);

        while (!antrean.isEmpty()) {
            String kota = antrean.poll();          // kunjungi node terdepan
            urutan.add(kota);
            for (String tetanggaKota : tetangga.get(kota)) {
                if (!dikunjungi.get(tetanggaKota)) {
                    dikunjungi.put(tetanggaKota, true);
                    antrean.offer(tetanggaKota);   // jadwalkan tetangga baru
                }
            }
        }
        return String.join(" -> ", urutan);
    }

    void cetakAdjacencyList() {
        for (Map.Entry<String, List<String>> e : tetangga.entrySet()) {
            System.out.println("  " + e.getKey() + ": " + e.getValue());
        }
    }
}