解题思路

这是一个图论问题,通过反向建图和拓扑排序来找到字典序最小的全排列。

关键点:

  1. 反向建图:将所有边反向,便于从大到小分配数字
  2. 使用最大堆维护可选节点
  3. 从n到1逆序分配数字,保证字典序最小

算法步骤:

  1. 建立反向图的邻接表
  2. 找出所有入度为 的点加入最大堆
  3. 每次取出堆顶元素,分配最大可用数字
  4. 更新邻接点的入度,将新的入度为 的点加入堆

代码

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    static const int MAXN = 100005;
    vector<int> graph[MAXN];
    vector<int> inDegree;
    vector<int> result;
    
public:
    void solve(int n, int m) {
        // 初始化
        inDegree.resize(n + 1, 0);
        result.resize(n + 1);
        
        // 读入边并建立反向图
        for (int i = 0; i < m; i++) {
            int from, to;
            cin >> from >> to;
            graph[to].push_back(from);
            inDegree[from]++;
        }
        
        // 拓扑排序
        priority_queue<int> maxHeap;
        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == 0) {
                maxHeap.push(i);
            }
        }
        
        // 分配数字
        int currentNum = n;
        while (!maxHeap.empty()) {
            int node = maxHeap.top();
            maxHeap.pop();
            
            result[node] = currentNum--;
            
            for (int next : graph[node]) {
                if (--inDegree[next] == 0) {
                    maxHeap.push(next);
                }
            }
        }
        
        // 输出结果
        printResult(n);
    }
    
private:
    void printResult(int n) {
        for (int i = 1; i <= n; i++) {
            cout << result[i];
            if (i < n) cout << " ";
        }
        cout << endl;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    Solution solution;
    solution.solve(n, m);
    
    return 0;
}
import java.util.*;

public class Main {
    static class Solution {
        private static final int MAXN = 100005;
        private List<Integer>[] graph;
        private int[] inDegree;
        private int[] result;
        
        @SuppressWarnings("unchecked")
        public void solve(Scanner sc) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            
            // 初始化
            graph = new ArrayList[MAXN];
            for (int i = 0; i < MAXN; i++) {
                graph[i] = new ArrayList<>();
            }
            inDegree = new int[n + 1];
            result = new int[n + 1];
            
            // 建立反向图
            for (int i = 0; i < m; i++) {
                int from = sc.nextInt();
                int to = sc.nextInt();
                graph[to].add(from);
                inDegree[from]++;
            }
            
            topologicalSort(n);
            printResult(n);
        }
        
        private void topologicalSort(int n) {
            PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
            
            // 找出入度为0的点
            for (int i = 1; i <= n; i++) {
                if (inDegree[i] == 0) {
                    maxHeap.offer(i);
                }
            }
            
            int currentNum = n;
            while (!maxHeap.isEmpty()) {
                int node = maxHeap.poll();
                result[node] = currentNum--;
                
                for (int next : graph[node]) {
                    if (--inDegree[next] == 0) {
                        maxHeap.offer(next);
                    }
                }
            }
        }
        
        private void printResult(int n) {
            StringBuilder sb = new StringBuilder();
            for (int i = 1; i <= n; i++) {
                sb.append(result[i]);
                if (i < n) sb.append(" ");
            }
            System.out.println(sb);
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        new Solution().solve(sc);
        sc.close();
    }
}
from heapq import heappush, heappop
from collections import defaultdict
from typing import List, Set

class Solution:
    def __init__(self):
        self.graph = defaultdict(list)
        self.in_degree = defaultdict(int)
        self.result = []
        
    def solve(self, n: int, m: int) -> None:
        # 读入边并建立反向图
        for _ in range(m):
            u, v = map(int, input().split())
            self.graph[v].append(u)
            self.in_degree[u] += 1
        
        self.topological_sort(n)
        self.print_result()
        
    def topological_sort(self, n: int) -> None:
        # 使用负数实现最大堆
        max_heap = []
        
        # 找出入度为0的点
        for i in range(1, n + 1):
            if self.in_degree[i] == 0:
                heappush(max_heap, -i)
        
        self.result = [0] * (n + 1)
        current_num = n
        
        while max_heap:
            node = -heappop(max_heap)
            self.result[node] = current_num
            current_num -= 1
            
            for next_node in self.graph[node]:
                self.in_degree[next_node] -= 1
                if self.in_degree[next_node] == 0:
                    heappush(max_heap, -next_node)
    
    def print_result(self) -> None:
        print(" ".join(map(str, self.result[1:])))

if __name__ == "__main__":
    n, m = map(int, input().split())
    Solution().solve(n, m)

算法及复杂度

  • 算法:拓扑排序 + 最大堆
  • 时间复杂度:
  • 空间复杂度: