题解 | 【模板】拓扑排序

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    vector<int> topoSort(int n, int m) {
        vector<vector<int>> adj(n + 1);  // 邻接表
        vector<int> inDegree(n + 1, 0);  // 入度数组
        vector<int> result;  // 结果数组
        
        // 读取边并构建图
        for(int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
            inDegree[v]++;
        }
        
        // 将所有入度为0的节点加入队列
        queue<int> q;
        for(int i = 1; i <= n; i++) {
            if(inDegree[i] == 0) {
                q.push(i);
            }
        }
        
        // BFS
        while(!q.empty()) {
            int curr = q.front();
            q.pop();
            result.push_back(curr);
            
            for(int next : adj[curr]) {
                inDegree[next]--;
                if(inDegree[next] == 0) {
                    q.push(next);
                }
            }
        }
        
        // 检查是否有环
        if(result.size() != n) {
            return vector<int>{-1};
        }
        
        return result;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    
    Solution sol;
    vector<int> result = sol.topoSort(n, m);
    
    // 输出结果
    if(result[0] == -1) {
        cout << -1;
    } else {
        for(int i = 0; i < result.size(); i++) {
            cout << result[i];
            if(i != result.size() - 1) cout << " ";
        }
    }
    
    return 0;
}

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

public class Main {
    public static void topoSort(int n, int m) throws IOException {
        // 使用BufferedReader加快输入
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        // 使用数组存储边
        int[][] edges = new int[m][2];
        int[] inDegree = new int[n + 1];
        ArrayList<Integer>[] adj = new ArrayList[n + 1];
        
        // 初始化邻接表
        for(int i = 1; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }
        
        // 读取边并构建图
        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            adj[u].add(v);
            inDegree[v]++;
        }
        
        // 将所有入度为0的节点加入队列
        Queue<Integer> q = new LinkedList<>();
        for(int i = 1; i <= n; i++) {
            if(inDegree[i] == 0) {
                q.offer(i);
            }
        }
        
        // 使用StringBuilder存储结果
        StringBuilder result = new StringBuilder();
        int count = 0;
        
        // BFS
        while(!q.isEmpty()) {
            int curr = q.poll();
            result.append(curr).append(" ");
            count++;
            
            for(int next : adj[curr]) {
                inDegree[next]--;
                if(inDegree[next] == 0) {
                    q.offer(next);
                }
            }
        }
        
        // 输出结果
        if(count != n) {
            System.out.print(-1);
        } else {
            // 删除最后一个空格
            System.out.print(result.substring(0, result.length() - 1));
        }
    }
    
    public static void main(String[] args) throws IOException {
        topoSort(0, 0);
    }
}

from collections import defaultdict, deque

def topoSort(n, m):
    # 构建邻接表和入度数组
    adj = defaultdict(list)
    inDegree = [0] * (n + 1)
    
    # 读取边并构建图
    for _ in range(m):
        u, v = map(int, input().split())
        adj[u].append(v)
        inDegree[v] += 1
    
    # 将所有入度为0的节点加入队列
    q = deque()
    for i in range(1, n + 1):
        if inDegree[i] == 0:
            q.append(i)
    
    result = []
    # BFS
    while q:
        curr = q.popleft()
        result.append(curr)
        
        for next_node in adj[curr]:
            inDegree[next_node] -= 1
            if inDegree[next_node] == 0:
                q.append(next_node)
    
    # 检查是否有环
    if len(result) != n:
        return [-1]
    
    return result

# 读取输入
n, m = map(int, input().split())
result = topoSort(n, m)

# 输出结果
if result[0] == -1:
    print(-1)
else:
    print(*result)