CSES - Strongly Connected Edges | Cạnh của đồ thị liên thông mạnh

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
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 để nhận được đồ thị có hướng liên thông mạ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 \(a\) và \(b\) với ý nghĩa có một cạnh nối giữa hai đỉnh \(a\) và \(b\).

Đồ thị đã cho là một đơn đồ thị. Tức là giữa hai đỉnh bất kỳ chỉ có tối đa một cạnh nối giữa chúng và tất cả các cạnh đều nối giữa hai đỉnh phân biệt.

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 ra phương án bất kỳ. Nếu không tồn tại đáp án, in ra IMPOSSIBLE.

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
1 3
2 3

Sample output

1 2
2 3
3 1

Bình luận


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

    Strongly Connected Edges | Cạnh liên thông mạ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 và liên thông mạ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 \(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\).

    Đồ thị đã cho là đơn đồ thị. Tức giữa hai đỉnh bất kì có tối đa một cạnh nối và mọi cạnh đều nối hai đỉnh phân biệt.

    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ì.
    • Nếu không tồn tại phương án, in ra IMPOSSIBLE.

    Example

    Test 1

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