解题思路
这是一个图论问题,通过反向建图和拓扑排序来找到字典序最小的全排列。
关键点:
- 反向建图:将所有边反向,便于从大到小分配数字
- 使用最大堆维护可选节点
- 从n到1逆序分配数字,保证字典序最小
算法步骤:
- 建立反向图的邻接表
- 找出所有入度为 的点加入最大堆
- 每次取出堆顶元素,分配最大可用数字
- 更新邻接点的入度,将新的入度为 的点加入堆
代码
#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)
算法及复杂度
- 算法:拓扑排序 + 最大堆
- 时间复杂度:
- 空间复杂度: