trang chủ / đề bài / icpc25_mt_e

Chia đồ thị

Đề bài

Mô tả

Cho một đồ thị vô hướng đơn gồm v đỉnh được đánh số từ 1 đến v và e cạnh.

Đồ thị được đảm bảo có một đỉnh x sao cho khoảng cách từ x đến mọi đỉnh khác không quá hai bước. Nói cách khác, mỗi đỉnh hoặc kề trực tiếp với x, hoặc kề với một đỉnh nào đó kề với x.

Nhiệm vụ của bạn là gán cho mỗi đỉnh một nhãn nhị phân (0 hoặc 1), tạo thành hai tập đỉnh rời nhau V0 và V1, cả hai đều khác rỗng, sao cho mỗi đỉnh có nhiều nhất một đỉnh kề mang nhãn khác với nó.

Nói cách khác, tập các cạnh nối hai đỉnh khác nhãn phải tạo thành một cặp ghép (không có hai cạnh nào trong số đó chung đỉnh).

Dữ liệu vào

  • Dòng đầu tiên gồm hai số nguyên v và e: số đỉnh và số cạnh.
  • Mỗi dòng trong e dòng tiếp theo gồm hai số nguyên a và b (1≤a,b≤v), cho biết có một cạnh vô hướng nối đỉnh a và đỉnh b.

Dữ liệu ra

  • Nếu không có cách gán nhãn hợp lệ, in ra −1.
  • Ngược lại, in ra một xâu nhị phân độ dài v, trong đó ký tự thứ i là 0 nếu đỉnh i thuộc V0 và là 1 nếu đỉnh i thuộc V1.

Nếu có nhiều cách gán nhãn hợp lệ, in ra một cách bất kỳ.

Ràng buộc

  • 2≤v≤106, 1≤e≤106, v×e≤2×106.
  • Đồ thị là đồ thị đơn (không có khuyên, không có cạnh lặp).
  • Tồn tại ít nhất một đỉnh x có khoảng cách đến mọi đỉnh khác không quá 2.

Ví dụ

Input Output Giải thích
6 8
1 3
1 6
2 1
2 3
2 4
3 4
4 5
5 6
000011 V1={5,6}. Các cạnh khác nhãn là (1,6) và (4,5), không chung đỉnh.
7 7
1 2
2 7
7 4
4 5
5 1
7 6
6 3
1000100 V1={1,5}. Các cạnh khác nhãn là (1,2) và (4,5).
6 8
1 2
1 6
2 6
2 3
6 4
6 5
4 5
5 3
-1 Không có cách chia hợp lệ.

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