CSES - Acyclic Graph Edges | Cạnh của DAG

Xem PDF
Tác giả:
nhphucqt
Dạng bài
Điểm: 1500 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một đồ thị vô hướng, nhiệm vụ của bạn là định chiều mỗi cạnh sao cho tạo thành được đồ thị có hướng không có chu trình.

Input

  • Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) lần lượt là số đỉnh và số cạnh. Các đỉnh được đánh chỉ số từ \(1\) đến \(n\).
  • \(m\) dòng tiếp theo mô tả danh sách cạnh. Mỗi dòng chứa hai số nguyên phân biệt \(a\) và \(b\) với ý nghĩa có một cạnh nối giữa đỉnh \(a\) và \(b\).

Output

  • In ra \(m\) dòng mô tả chiều của các cạnh. Mỗi dòng chứa hai số nguyên \(a\) và \(b\) với ý nghĩa có một cung nối từ đỉnh \(a\) đến đỉnh \(b\). Bạn có thể in bất kỳ đáp án nào thỏa mãn.

Constraints

  • \(1 \le n \le 10^5\)
  • \(1 \le m \le 2 \times 10^5\)
  • \(1 \le a, b \le n\)

Example

Sample input

3 3
1 2
2 3
3 1

Sample output

1 2
3 2
3 1

Bình luận


  • -1
    nguyen_ducminh    1:20 a.m. 31 Tháng 8, 2023 ← đã chỉnh sửa

    Acyclic Graph Edges | Cạnh của đồ thị không chu trình

    Bạn được cho một đồ thị vô hướng, nhiệm vụ của bạn là định chiều cho mỗi cạnh sao cho đồ thị ban đầu trở thành đồ thị có hướng không chu trình.

    Input

    • Dòng đầu tiên gồm hai số nguyên \(n\) (\(1 \leq n \leq 10^5\)) và \(m\) (\(1 \leq m \leq 2\times10^5\)) - số lượng đỉnh và cạnh của cây. Các đỉnh được đánh chỉ số \(1,2,...,n\).
    • \(m\) dòng tiếp theo mô tả các cạnh. Mỗi dòng gồm hai số nguyên phân biệt \(a\) và \(b\) (\(1 \leq a,b \leq n\)) với ý nghĩa có cạnh nối giữa hai đỉnh \(a\) và \(b\).

    Output

    • Gồm \(m\) dòng mô tả chiều của các cung. Mỗi dòng gồm hai số nguyên \(a\) và \(b\) với ý nghĩa có cung nối từ đỉnh \(a\) tới đỉnh \(b\). Bạn có thể in ra một phương án hợp lệ bất kì.

    Example

    Test 1

    Input 
    3 3
1 2
2 3
3 1
    Output 
    1 2
3 2
3 1