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

public class DfsSiklus {

    // Warna status DFS pada directed graph:
    // 1 = putih (belum dikunjungi), 2 = abu-abu (sedang diproses), 3 = hitam (selesai).
    private static final int PUTIH = 1, ABU = 2, HITAM = 3;

    private final Map<String, List<String>> sisi = new LinkedHashMap<>();
    private final Map<String, Integer> status = new LinkedHashMap<>();

    public static void main(String[] args) {
        DfsSiklus matakuliah = new DfsSiklus();
        matakuliah.prasyarat("DasarPemrograman", "OOP");
        matakuliah.prasyarat("DasarPemrograman", "StrukturData");
        matakuliah.prasyarat("StrukturData", "Algoritma");
        matakuliah.prasyarat("OOP", "BasisData");
        matakuliah.prasyarat("Algoritma", "KeamananAplikasi");

        System.out.println("=== Kartu rencana studi tanpa siklus ===");
        System.out.println("Siklus terdeteksi: " + matakuliah.adaSiklus());

        // Tambahkan prasyarat balik: Algoritma menuntut DasarPemrograman.
        matakuliah.prasyarat("Algoritma", "DasarPemrograman");

        System.out.println();
        System.out.println("=== Setelah menambah sisi Algoritma -> DasarPemrograman ===");
        System.out.println("Siklus terdeteksi: " + matakuliah.adaSiklus());
    }

    void prasyarat(String dari, String ke) {
        sisi.computeIfAbsent(dari, k -> new ArrayList<>()).add(ke);
        sisi.computeIfAbsent(ke, k -> new ArrayList<>());
    }

    boolean adaSiklus() {
        for (String node : sisi.keySet()) {
            status.put(node, PUTIH);
        }
        for (String node : sisi.keySet()) {
            if (status.get(node) == PUTIH && dfsDeteksi(node)) {
                return true;
            }
        }
        return false;
    }

    // DFS rekursif: node berstatus abu-abu berarti node itu berada
    // di jalur penelusuran saat ini, jadi sisi menuju node itu menutup siklus.
    private boolean dfsDeteksi(String node) {
        status.put(node, ABU);
        for (String tujuan : sisi.get(node)) {
            if (status.get(tujuan) == ABU) {
                System.out.println("  Sisi " + node + " -> " + tujuan
                        + " kembali ke node yang masih diproses");
                return true;
            }
            if (status.get(tujuan) == PUTIH && dfsDeteksi(tujuan)) {
                return true;
            }
        }
        status.put(node, HITAM);
        return false;
    }
}