拓扑排序与依赖关系

def eventual_safe_nodes(graph: list[list[int]]) -> list[int]:
    """Nodes every path from which ends at a terminal node: no cycle is reachable (LC 802)."""
    WHITE, GRAY, BLACK = 0, 1, 2  # unvisited / on the current DFS path / finished and safe
    color = [WHITE] * len(graph)

    def safe(u: int) -> bool:
        if color[u] != WHITE:
            return color[u] == BLACK  # GRAY: back on the current path, so a cycle
        color[u] = GRAY
        if not all(safe(v) for v in graph[u]):
            return False  # stays GRAY: on a cycle or leading to one
        color[u] = BLACK
        return True

    return [u for u in range(len(graph)) if safe(u)]

// Nodes every path from which ends at a terminal node: no cycle is reachable (LC 802).
vector<int> eventualSafeNodes(const vector<vector<int>>& graph) {
    enum { WHITE, GRAY, BLACK };  // unvisited / on the current DFS path / finished and safe
    vector<int> color(graph.size(), WHITE);
    function<bool(int)> safe = [&](int u) {
        if (color[u] != WHITE) return color[u] == BLACK;  // GRAY: back on the current path, so a cycle
        color[u] = GRAY;
        for (int v : graph[u])
            if (!safe(v)) return false;  // stays GRAY: on a cycle or leading to one
        color[u] = BLACK;
        return true;
    };
    vector<int> res;
    for (int u = 0; u < (int)graph.size(); u++)
        if (safe(u)) res.push_back(u);
    return res;
}

class Solution {
    private static final int WHITE = 0, GRAY = 1, BLACK = 2; // unvisited / on the current DFS path / finished and safe
    private int[][] graph;
    private int[] color;

    // Nodes every path from which ends at a terminal node: no cycle is reachable (LC 802).
    List<Integer> eventualSafeNodes(int[][] graph) {
        this.graph = graph;
        color = new int[graph.length];
        List<Integer> res = new ArrayList<>();
        for (int u = 0; u < graph.length; u++)
            if (safe(u)) res.add(u);
        return res;
    }

    private boolean safe(int u) {
        if (color[u] != WHITE) return color[u] == BLACK; // GRAY: back on the current path, so a cycle
        color[u] = GRAY;
        for (int v : graph[u])
            if (!safe(v)) return false; // stays GRAY: on a cycle or leading to one
        color[u] = BLACK;
        return true;
    }
}

// eventualSafeNodes returns the nodes every path from which ends at a terminal node (LC 802).
func eventualSafeNodes(graph [][]int) []int {
	const (
		white = iota // unvisited
		gray         // on the current DFS path
		black        // finished and safe
	)
	color := make([]int, len(graph))
	var safe func(u int) bool
	safe = func(u int) bool {
		if color[u] != white {
			return color[u] == black // gray: back on the current path, so a cycle
		}
		color[u] = gray
		for _, v := range graph[u] {
			if !safe(v) {
				return false // stays gray: on a cycle or leading to one
			}
		}
		color[u] = black
		return true
	}
	res := []int{}
	for u := range graph {
		if safe(u) {
			res = append(res, u)
		}
	}
	return res
}

from collections import deque


def min_semesters(n: int, relations: list[tuple[int, int]]) -> int:
    """Courses 1..n, (a, b): a before b, any number per term. Fewest terms, or -1 on a cycle (LC 1136)."""
    graph = [[] for _ in range(n + 1)]
    indeg = [0] * (n + 1)
    for a, b in relations:
        graph[a].append(b)
        indeg[b] += 1
    term = [1] * (n + 1)  # term[v]: the earliest term v can be taken
    q = deque(v for v in range(1, n + 1) if indeg[v] == 0)
    done = 0
    while q:
        u = q.popleft()
        done += 1
        for v in graph[u]:
            term[v] = max(term[v], term[u] + 1)  # DP in topological order: u is final when it leaves
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return max(term[1:]) if done == n else -1

// Courses 1..n, {a, b}: a before b, any number per term. Fewest terms, or -1 on a cycle (LC 1136).
int minSemesters(int n, const vector<pair<int, int>>& relations) {
    vector<vector<int>> graph(n + 1);
    vector<int> indeg(n + 1, 0), term(n + 1, 1);  // term[v]: the earliest term v can be taken
    for (auto [a, b] : relations) {
        graph[a].push_back(b);
        indeg[b]++;
    }
    queue<int> q;
    for (int v = 1; v <= n; v++)
        if (indeg[v] == 0) q.push(v);
    int done = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        done++;
        for (int v : graph[u]) {
            term[v] = max(term[v], term[u] + 1);  // DP in topological order: u is final when it leaves
            if (--indeg[v] == 0) q.push(v);
        }
    }
    return done == n ? *max_element(term.begin() + 1, term.end()) : -1;
}

class Solution {
    // Courses 1..n, {a, b}: a before b, any number per term. Fewest terms, or -1 on a cycle (LC 1136).
    int minSemesters(int n, int[][] relations) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
        int[] indeg = new int[n + 1], term = new int[n + 1]; // term[v]: the earliest term v can be taken
        Arrays.fill(term, 1);
        for (int[] r : relations) {
            graph.get(r[0]).add(r[1]);
            indeg[r[1]]++;
        }
        Deque<Integer> q = new ArrayDeque<>();
        for (int v = 1; v <= n; v++)
            if (indeg[v] == 0) q.offer(v);
        int done = 0, best = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            done++;
            best = Math.max(best, term[u]);
            for (int v : graph.get(u)) {
                term[v] = Math.max(term[v], term[u] + 1); // DP in topological order: u is final when it leaves
                if (--indeg[v] == 0) q.offer(v);
            }
        }
        return done == n ? best : -1;
    }
}

// minSemesters returns the fewest terms for courses 1..n ({a, b}: a before b), or -1 on a cycle.
func minSemesters(n int, relations [][2]int) int {
	graph := make([][]int, n+1)
	indeg, term := make([]int, n+1), make([]int, n+1) // term[v]: the earliest term v can be taken
	for _, r := range relations {
		graph[r[0]] = append(graph[r[0]], r[1])
		indeg[r[1]]++
	}
	var q []int
	for v := 1; v <= n; v++ {
		term[v] = 1
		if indeg[v] == 0 {
			q = append(q, v)
		}
	}
	done, best := 0, 0
	for len(q) > 0 {
		u := q[0]
		q = q[1:]
		done++
		best = max(best, term[u])
		for _, v := range graph[u] {
			term[v] = max(term[v], term[u]+1) // DP in topological order: u is final when it leaves
			indeg[v]--
			if indeg[v] == 0 {
				q = append(q, v)
			}
		}
	}
	if done != n {
		return -1
	}
	return best
}