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

    // Lớp nội bộ để triển khai hàng đợi
    private class Queue {
        private final int[] elements;
        private int front, rear, size;

        public Queue(int capacity) {
            elements = new int[capacity];
            front = 0;
            rear = -1;
            size = 0;
        }

        public void enqueue(int item) {
            rear = (rear + 1) % elements.length;
            elements[rear] = item;
            size++;
        }

        public int dequeue() {
            int item = elements[front];
            front = (front + 1) % elements.length;
            size--;
            return item;
        }

        public boolean isEmpty() {
            return size == 0;
        }
    }

    // Constructor để khởi tạo đồ thị với V đỉnh
    public Graph(int V) {
        this.V = V;
        adj = new int[V][V];
        inDegree = new int[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;
        inDegree[dest]++;
    }

    // Phương thức kiểm tra chu trình trong đồ thị
    public boolean isCyclic() {
        Queue queue = new Queue(V);  // Tạo hàng đợi với kích thước V
        int[] tempInDegree = new int[V];
        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.enqueue(i);
            }
        }

        int visitedVertices = 0;

        // Trong khi hàng đợi không rỗng
        while (!queue.isEmpty()) {
            int current = queue.dequeue();  // Lấy đỉnh từ đầu hàng đợi
            visitedVertices++;

            // 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.enqueue(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");
        }
    }
}