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 nm — số đỉnh và số cạnh.
  • m dòng tiếp theo, mỗi dòng chứa hai số nguyên uv (1u,vn, uv) mô tả một cạnh nối đỉnh uv. 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

  • 1n100000
  • 0mmin(n(n1)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}{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.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0