记录一下江苏银行笔试的代码题 课程前置问题

第一行给2个数字n和m，n表示课程总数，m表示依赖关系数量；

接下来是m行，第0个数为当前课程，第1个数为前置课程。

要求判断它能否学习完所有的课程。

解决方法是要构造一个图，然后拓扑排序一下。

正确解法：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt(); // 课程总数
        int m = cin.nextInt(); // 依赖关系数量

        // 构建邻接表
        List<List<Integer>> adj = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        // 构建入度数组
        int[] inDegree = new int[n];

        for (int i = 0; i < m; i++) {
            int course = cin.nextInt();
            int pre = cin.nextInt();
            adj.get(pre).add(course);
            inDegree[course]++;
        }

        // 使用拓扑排序检测循环依赖
        if (hasCycle(adj, inDegree, n)) {
            System.out.println("False");
        } else {
            System.out.println("True");
        }
    }

    private static boolean hasCycle(List<List<Integer>> adj, int[] inDegree, int n) {
        Queue<Integer> queue = new LinkedList<>();
        int count = 0; // 记录已经访问的节点数量

        // 将所有入度为 0 的节点加入队列
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int u = queue.poll();
            count++;

            // 遍历 u 的所有邻居
            for (int v : adj.get(u)) {
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    queue.offer(v);
                }
            }
        }

        // 如果访问的节点数量小于总节点数量，则说明存在环
        return count != n;
    }
}

---分割线---

import java.io.*;
import java.util.*;

public class Main
{
    public static void main(String args[])
    {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int m = cin.nextInt();
        
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<m;i++){
          int module = cin.nextInt();
          int pre = cin.nextInt();
          map.put(pre,module);
          int cur = module;
          while(map.getOrDefault(cur,-1)!=-1){
            if(cur==pre){
              System.out.println("False");
              return;
            }
            cur = map.get(cur);
          }
        }
      
        System.out.println("True");
    }
}