from collections import defaultdict,deque
N = int(input())
edges = defaultdict(list)
indeg = [0]*(N+1)
for i in range(1,N+1):
    data = list(map(int,input().split()))
    n = int(data[0])
    for j in range(1,n+1):
        edges[data[j]].append(i)
        indeg[i]+=1
q = deque(u for u in range(1,N+1) if indeg[u]==0)

cnt = 0
deth = [0]*(N+1)
while q:
    u = q.popleft()
    cnt+=1
    for v in edges[u]:
        indeg[v]-=1
        if indeg[v]==0:
            q.append(v)
            deth[v]=deth[u]+1
if cnt !=N:
    print(-1)
else:
    print(max(deth)+1)

可能不怎么规范的拓扑

#include<bits/stdc++.h>
using namespace std;
int rd[1010];
bool book[1010];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin>>n;
	vector<int>a[n+1];
	for(int i=1;i<=n;i++){
		int k;cin>>k;
		for(int j=1;j<=k;j++){
			int x;cin>>x;
			a[x].push_back(i);
			rd[i]++;
		}
	}
	int cnt=0;
	bool fg;
	while(1){
		queue<int>que;
		fg=0;
		for(int i=1;i<=n;i++)
			if(rd[i]==0&&book[i]==0){
				que.push(i);
				book[i]=1;
			}
			else if(rd[i]!=0) fg=1;
		if(que.empty())break;
		cnt++;
		while(!que.empty()){
			for(auto&x:a[que.front()])rd[x]--;
			que.pop();
		}
	}
	if(fg)cout<<-1;
	else cout<<cnt;
	return 0;
}

题面描述:

题目要求计算给定模块间的依赖关系所需的最少“批量构建”次数，输入由一个正整数 $N$ 表示模块总数，接下来的 $N$ 行描述每个模块的依赖关系，第一项是该模块依赖的模块数量，后续项是具体的模块编号。如果存在循环依赖导致无法完成构建，则输出 $-1$；如果没有，则输出所需的最少“批量构建”次数。例如，对于输入 5\n3 2 3 4\n1 5\n1 5\n1 5\n0，输出应为 3；对于输入 3\n1 2\n1 3\n1 1，输出应为 -1。

思路

可以使用拓扑排序来解决。

将每个模块看作图中的一个节点，如果模块 $A$ 依赖模块 $B$，则在图中添加一条从 $B$ 指向 $A$ 的有向边。

用 $cnt$ 来记录节点入队的次数，$dep[i]$ 表示节点 $i$ 的深度，记所有初始入度为 0 的点深度为 0。

如果最后 $cnt$ 的数量不等于 $n$ ，则表示不能循环依赖，否则最后的答案为 $max(dep[i])$ $(1 \le i \le n)$

主要步骤

1. 建图：

   • 使用邻接表 graph 存储模块之间的依赖关系。
   • 使用数组 d 来记录每个模块的入度（即有多少模块依赖于该模块）。如果一个模块的入度为 0，表示它可以独立构建。

2. 初始化：

   • 遍历输入数据，构建邻接表和入度数组。对于每个模块 $i$，如果它依赖于模块 $x$，则在 graph[x] 中添加一条从 $x$ 到 $i$ 的边，并将模块 $i$ 的入度加 1。

3. 拓扑排序：

   • 使用双端队列 q 存储当前所有入度为 0 的模块。初始化时，将所有入度为 0 的模块加入队列。
   • 记录处理的节点数量 cnt 和每个节点的深度 dep。深度代表在构建过程中当前模块需要被构建的层级。

4. 处理节点：

   • 通过队列逐个处理模块。每当从队列中取出一个节点时，将 cnt 增加 1，并遍历它的所有邻接节点，将邻接节点的入度减 1。
   • 如果邻接节点的入度减到 0，则将其加入队列，并更新它的深度为当前节点深度加 1。

5. 检测循环依赖：

   • 如果 cnt 的数量不等于模块总数 $n$，则说明存在循环依赖，输出 -1。
   • 否则，输出 dep 数组中的最大值加 1（因为深度是从 0 开始的，代表的构建层级）。

AC代码

• Python

from collections import deque

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    # 获取节点数 n
    idx = 0
    n = int(data[idx])
    idx += 1
    
    # 初始化入度数组 d 和邻接表 graph
    d = [0] * (n + 1)
    graph = [[] for _ in range(n + 1)]
    
    # 构建邻接表和入度数组
    for i in range(1, n + 1):
        k = int(data[idx])
        idx += 1
        while k > 0:
            k -= 1
            x = int(data[idx])
            idx += 1
            graph[x].append(i)
            d[i] += 1
    
    # 执行拓扑排序
    q = deque()
    for i in range(1, n + 1):
        # 将所有入度为0的节点加入队列
        if d[i] == 0:
            q.append(i)
    cnt = 0 # 记录节点入队次数
    dep = [0] * (n + 1) # 记录每个节点的深度
    while q:
        # 从队列中取出一个节点
        t = q.popleft()
        cnt += 1 
        # 遍历该节点的所有邻接节点
        for i in graph[t]:
            # 将邻接节点的入度减1
            d[i] -= 1
            # 如果邻接节点的入度变为0,则加入队列
            if d[i] == 0:
                q.append(i)
                # 更新邻接节点的深度
                dep[i] = dep[t] + 1
    
    # 判断是否存在循环依赖
    if cnt != n: 
        print(-1) 
    else:
        print(max(dep) + 1)

if __name__ == "__main__":
    main()

• CPP

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
    // 获取节点数 n
    int n;
    cin >> n;
    
    // 初始化入度数组 d 和邻接表 graph
    vector<int> d(n + 1, 0);
    vector<vector<int>> graph(n + 1);
    
    // 构建邻接表和入度数组
    for (int i = 1; i <= n; ++i) {
        int k;
        cin >> k;
        while (k > 0) {
            --k;
            int x;
            cin >> x;
            graph[x].push_back(i);
            d[i]++;
        }
    }
    
    // 执行拓扑排序
    deque<int> q;
    for (int i = 1; i <= n; ++i) {
        // 将所有入度为0的节点加入队列
        if (d[i] == 0) {
            q.push_back(i);
        }
    }

    int cnt = 0; // 记录节点入队次数
    vector<int> dep(n + 1, 0); // 记录每个节点的深度
    while (!q.empty()) {
        // 从队列中取出一个节点
        int t = q.front();
        q.pop_front();
        cnt++;
        // 遍历该节点的所有邻接节点
        for (int i : graph[t]) {
            // 将邻接节点的入度减1
            d[i]--;
            // 如果邻接节点的入度变为0,则加入队列
            if (d[i] == 0) {
                q.push_back(i);
                // 更新邻接节点的深度
                dep[i] = dep[t] + 1;
            }
        }
    }
    
    // 判断是否存在循环依赖
    if (cnt != n) {
        cout << -1 << endl;
    } else {
        cout << *max_element(dep.begin(), dep.end()) + 1 << endl;
    }
    
    return 0;
}

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 创建 Scanner 对象读取输入
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        // 初始化入度数组 d 和邻接表 graph
        int[] d = new int[n + 1];
        List<Integer>[] graph = new ArrayList[n + 1];
        
        // 构建邻接表和入度数组
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        
        for (int i = 1; i <= n; i++) {
            int k = sc.nextInt();
            while (k > 0) {
                k--;
                int x = sc.nextInt();
                graph[x].add(i);
                d[i]++;
            }
        }
        
        // 执行拓扑排序
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) {
            // 将所有入度为0的节点加入队列
            if (d[i] == 0) {
                q.add(i);
            }
        }

        int cnt = 0; // 记录节点入队次数
        int[] dep = new int[n + 1]; // 记录每个节点的深度
        while (!q.isEmpty()) {
            // 从队列中取出一个节点
            int t = q.poll();
            cnt++;
            // 遍历该节点的所有邻接节点
            for (int i : graph[t]) {
                // 将邻接节点的入度减1
                d[i]--;
                // 如果邻接节点的入度变为0,则加入队列
                if (d[i] == 0) {
                    q.add(i);
                    // 更新邻接节点的深度
                    dep[i] = dep[t] + 1;
                }
            }
        }
        
        // 判断是否存在循环依赖
        if (cnt != n) {
            System.out.println(-1);
        } else {
            System.out.println(Arrays.stream(dep).max().getAsInt() + 1);
        }
        
        // 关闭 Scanner 对象
        sc.close();
    }
}