moi_an_cuoi_solu_java

 avatar
SSkyFire
java
2 months ago
3.1 kB
1
Indexable
Never
import java.io.*;
import java.util.*;

public class Main {
    static int T, N, M, v_start, v_end;
    static int[][] canh = new int[1005][2];
    static int[] cnt = new int[105]; // Số cạnh kề với mỗi đỉnh
    static int[][] canhke = new int[105][105]; // Lưu cạnh kề
    static int res = 0; // Kết quả
    static int[] visited = new int[105]; // Kiểm tra đỉnh đã được thăm hay chưa
    static int[] trace = new int[105]; // Lưu vết đường đi
    static int[] ans = new int[105]; // Đếm số lần xuất hiện của mỗi đỉnh trong tất cả đường đi
    static int k; // Số đường đi từ đỉnh bắt đầu tới đỉnh kết thúc

    public static void dfs(int u, int count) {
        if (u == v_end) {
            // Đã đến đỉnh cuối, cập nhật ans cho các đỉnh trên đường đi
            for (int i = 0; i < count; i++) {
                ans[trace[i]]++;
            }
            k++; // Tăng số lượng đường đi tìm được
            return;
        }

        // Duyệt qua tất cả các đỉnh kề với u
        for (int i = 0; i < cnt[u]; i++) {
            if (visited[canhke[u][i]] == 0) {
                visited[canhke[u][i]] = 1; // Đánh dấu đã thăm
                trace[count] = canhke[u][i]; // Ghi nhận đỉnh vào đường đi
                dfs(canhke[u][i], count + 1); // Đệ quy tiếp tục tìm đường đi
                // Backtrack
                trace[count] = 0; 
                visited[canhke[u][i]] = 0; // Bỏ đánh dấu
            }
        }
    }

    public static void main(String[] args) throws FileNotFoundException {
        Scanner scanner = new Scanner(new File("input.txt"));
        T = scanner.nextInt(); // Đọc số lượng test case
        for (int tc = 1; tc <= T; tc++) {
            k = 0; // Reset cho mỗi test case
            res = 0;
            N = scanner.nextInt();
            M = scanner.nextInt();
            v_start = scanner.nextInt();
            v_end = scanner.nextInt();
            // Khởi tạo mảng
            Arrays.fill(cnt, 0);
            Arrays.fill(visited, 0);
            Arrays.fill(ans, 0);
            
            for (int i = 0; i < M; i++) {
                canh[i][0] = scanner.nextInt();
                canh[i][1] = scanner.nextInt();
                // Xây dựng danh sách kề
                canhke[canh[i][0]][cnt[canh[i][0]]++] = canh[i][1];
            }
            visited[v_start] = 1; // Đánh dấu điểm bắt đầu
            trace[0] = v_start; // Khởi tạo đường đi
            dfs(v_start, 1); // Bắt đầu DFS

            // Đếm và in ra kết quả
            for (int i = 0; i <= N; i++) {
                if (ans[i] == k) {
                    res++;
                }
            }
            System.out.println(res - 2); // In ra kết quả, trừ đi đầu và cuối
        }
        scanner.close();
    }
}
Leave a Comment