trang chủ / đề bài / gr09_topo

Sắp xếp topo

Đề bài

Mô tả

Cho đồ thị có hướng gồm n đỉnh đánh số từ 1 đến n và m cung; cung thứ i đi từ đỉnh ui tới đỉnh vi. Có thể có cung từ một đỉnh tới chính nó và nhiều cung giữa cùng một cặp đỉnh.

Hãy sắp xếp tất cả các đỉnh thành một dãy sao cho với mọi cung u→v, đỉnh u đứng trước đỉnh v trong dãy. Nếu không thể sắp xếp như vậy, hãy thông báo.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên n, m.
  • m dòng tiếp theo, dòng thứ i chứa hai số nguyên ui,vi.

Dữ liệu ra

Nếu sắp xếp được, in ra trên một dòng n số nguyên phân biệt từ 1 đến n là dãy đỉnh tìm được, cách nhau bởi dấu cách. Nếu có nhiều dãy thỏa mãn, in ra dãy bất kỳ.

Nếu không sắp xếp được, in ra -1.

Ràng buộc

  • 1≤n≤105
  • 0≤m≤2·105
  • 1≤ui,vi≤n

Ví dụ

Input Output Giải thích
6 7
5 2
1 2
2 3
6 3
1 4
4 3
5 6
1 5 4 2 6 3 Mọi cung đều đi từ trái sang phải trong dãy. Các dãy khác như 5 6 1 2 4 3 cũng được chấp nhận.
4 4
1 2
2 3
3 4
4 2
-1 Các cung 2→3→4→2 tạo thành chu trình: đỉnh nào trong ba đỉnh này đứng đầu dãy thì cung đi vào nó đều bị ngược chiều.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0