LeetCode 补充题 23. 检测循环依赖

Categories:

题目描述
思路分析
1. 解法一：拓扑排序判环（推荐）
相似题目

题目描述

✅ 补充题 23. 检测循环依赖

思路分析

解法一：拓扑排序判环（推荐）

核心思路：

将依赖关系看作有向图，是否存在环等价于是否能完成拓扑排序。

统计每个节点入度，入度为 0 的节点入队。

逐步删除入度为 0 的节点并减少其邻居入度。

最终处理节点数等于总节点数则无环，否则有环。

复杂度分析：

时间复杂度：O(V + E)，其中 V、E 分别为节点数与依赖边数。

空间复杂度：O(V + E)，用于邻接表与队列。

import java.util.*;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegree = new int[numCourses];
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }

        for (int[] p : prerequisites) {
            graph.get(p[1]).add(p[0]);
            indegree[p[0]]++;
        }

        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        int count = 0;
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            count++;
            for (int next : graph.get(cur)) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        return count == numCourses;
    }
}

func canFinish(numCourses int, prerequisites [][]int) bool {
	indegree := make([]int, numCourses)
	graph := make([][]int, numCourses)

	for _, p := range prerequisites {
		graph[p[1]] = append(graph[p[1]], p[0])
		indegree[p[0]]++
	}

	queue := make([]int, 0)
	for i := 0; i < numCourses; i++ {
		if indegree[i] == 0 {
			queue = append(queue, i)
		}
	}

	count := 0
	for len(queue) > 0 {
		cur := queue[0]
		queue = queue[1:]
		count++
		for _, next := range graph[cur] {
			indegree[next]--
			if indegree[next] == 0 {
				queue = append(queue, next)
			}
		}
	}

	return count == numCourses
}

相似题目

题目	难度	考察点
207. 课程表	中等	拓扑排序
210. 课程表 II	中等	拓扑排序
802. 找到最终的安全状态	中等	拓扑排序
684. 冗余连接	中等	并查集
785. 判断二分图	中等	图遍历

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/88516177