Untitled

class Graph {
    private final int V;  // Số lượng đỉnh
    private final int[][] adj;  // Ma trận kề để lưu các cạnh
    private final int[] inDegree;  // Mảng lưu bậc trong của mỗi đỉnh

    // Constructor để khởi tạo đồ thị với V đỉnh
    public Graph(int V) {
        this.V = V;
        adj = new int[V][V];  // Khởi tạo ma trận kề với kích thước V x V
        inDegree = new int[V];  // Khởi tạo mảng bậc trong với kích thước V
    }

    // Phương thức thêm cạnh từ 'source' đến 'dest'
    public void addEdge(int source, int dest) {
        adj[source][inDegree[source]++] = dest;  // Thêm 'dest' vào danh sách kề của 'source'
        inDegree[dest]++;  // Tăng bậc trong của 'dest'
    }

    // Phương thức kiểm tra chu trình trong đồ thị
    public boolean isCyclic() {
        int[] queue = new int[V];  // Mảng dùng làm hàng đợi để lưu các đỉnh có bậc trong bằng 0
        int front = 0, rear = 0;  // Con trỏ đầu và cuối hàng đợi
        int[] tempInDegree = new int[V];  // Bản sao tạm thời của mảng bậc trong

        // Sao chép mảng bậc trong vào mảng tạm thời
        System.arraycopy(inDegree, 0, tempInDegree, 0, V);

        // Thêm các đỉnh có bậc trong bằng 0 vào hàng đợi
        for (int i = 0; i < V; i++) {
            if (tempInDegree[i] == 0) {
                queue[rear++] = i;  // Đẩy đỉnh vào hàng đợi
            }
        }

        int visitedVertices = 0;  // Đếm số đỉnh đã duyệt

        // Trong khi hàng đợi không rỗng
        while (front != rear) {
            int current = queue[front++];  // Lấy đỉnh từ đầu hàng đợi
            visitedVertices++;  // Tăng số lượng đỉnh đã duyệt

            // Kiểm tra tất cả các đỉnh kề của đỉnh hiện tại
            for (int i = 0; i < V; i++) {
                if (adj[current][i] != 0) {  // Nếu có cạnh từ current đến i
                    if (--tempInDegree[i] == 0) {
                        queue[rear++] = i;  // Thêm đỉnh kề vào hàng đợi nếu bậc trong của nó bằng 0
                    }
                }
            }
        }

        // Nếu số lượng đỉnh đã duyệt khác số lượng đỉnh của đồ thị, thì có chu trình
        return visitedVertices != V;
    }

    // Phương thức chính để kiểm tra đồ thị
    public static void main(String[] args) {
        Graph graph = new Graph(4);  // Tạo đồ thị với 4 đỉnh
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

        // Kiểm tra và in ra liệu đồ thị có chu trình hay không
        if (graph.isCyclic()) {
            System.out.println("Đồ thị có chu trình");
        } else {
            System.out.println("Đồ thị không có chu trình");
        }
    }
}