Cạnh trên Chu trình Đơn Duy nhất

Đề bài

Mô tả

Cho một đồ thị vô hướng gồm n đỉnh và m cạnh. Đồ thị không nhất thiết liên thông, không chứa cạnh kép (không có nhiều hơn một cạnh giữa cùng một cặp đỉnh) và không chứa khuyên (cạnh nối một đỉnh với chính nó).

Một chu trình đơn trong đồ thị là một chu trình mà mỗi đỉnh xuất hiện đúng một lần trong chu trình đó.

Hãy xác định những cạnh thuộc về đúng một chu trình đơn của đồ thị.

Dữ liệu vào

  • Dòng đầu chứa hai số nguyên n và m — số đỉnh và số cạnh.
  • m dòng tiếp theo, mỗi dòng chứa hai số nguyên u và v (1≤u,v≤n, u≠v) mô tả một cạnh nối đỉnh u và v. Các cạnh được đánh số từ 1 theo thứ tự xuất hiện trong dữ liệu vào.

Dữ liệu ra

  • Dòng đầu in ra số lượng cạnh thuộc đúng một chu trình đơn.
  • Dòng thứ hai in ra chỉ số của các cạnh này theo thứ tự tăng dần, cách nhau bởi dấu cách. Nếu không có cạnh nào thoả mãn thì bỏ qua dòng này.

Ràng buộc

  • 1≤n≤100000
  • 0≤m≤min(n(n−1)2, 100000)

Ví dụ

Input Output Giải thích
6 7
2 3
3 4
4 2
1 2
1 5
5 6
6 1
6
1 2 3 5 6 7
Đồ thị có hai tam giác rời nhau (đỉnh {2,3,4} và {1,5,6} — lưu ý cạnh 1-2 là cầu, không nằm trong chu trình nào). Cả 6 cạnh của hai tam giác đều thuộc đúng một chu trình đơn.
3 3
1 2
2 3
3 1
3
1 2 3
Cả ba cạnh tạo thành một tam giác — chu trình đơn duy nhất.
5 6
1 2
2 3
2 4
4 3
2 5
5 3
0 Đồ thị chứa nhiều chu trình đơn nhưng tất cả các cạnh đều được chia sẻ giữa ít nhất hai chu trình, nên không cạnh nào thuộc đúng một chu trình đơn.

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