CSES - Course Schedule II | Xếp lịch khóa học II
Xem PDF
Điểm:
1700 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Bạn muốn hoàn thành \(n\) khóa học có yêu cầu dạng "khóa học \(a\) phải được hoàn thành trước khóa học \(b\)".
Bạn muốn hoàn thành khóa học \(1\) càng sớm càng tốt. Nếu có nhiều cách để làm, bạn muốn hoàn thành khóa học \(2\) càng sớm càng tốt, v.v.
Nhiệm vụ của bạn là xác định thứ tự mà bạn hoàn thành các khóa học.
Input:
- Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số lượng khóa học và số yêu cầu. Các khóa học được đánh số \(1,2,…, n\).
- Sau đó, có \(m\) dòng mô tả các yêu cầu. Mỗi dòng có hai số nguyên \(a\) và \(b\): khóa học \(a\) phải được hoàn thành trước khóa học \(b\).
- Dữ liệu đảm bảo có ít nhất một lịch trình hợp lệ.
Output:
- Một dòng duy nhất chứa \(n\) số nguyên: thứ tự hoàn thành các khóa học.
Constraints
- \(1\leq n \leq 10^5\)
- \(1\leq m \leq 2 ⋅ 10^5\)
- \(1\leq a, b \leq n\)
Test 1
Input
4 2
2 1
2 3Output
2 1 3 4
Bình luận
Bạn muốn hoàn thành \(n\) khóa học có yêu cầu dạng "Khóa học \(a\) phải được hoàn thành trước khóa học \(b\)".
Bạn muốn hoàn thành khóa học \(1\) càng sớm càng tốt. Nếu có nhiều cách để làm, bạn muốn hoàn thành khóa học \(2\) càng sớm càng tốt, v.v.
Nhiệm vụ của bạn là xác định thứ tự mà bạn hoàn thành các khóa học.
Input:
Output:
Example
Test 1
Input
Output
Dùng Khan's Algorithm pass được có 2 test 😀, mà lại không biết làm DFS, buồn thật chứ.