#1014. VALG - Giá trị lớn nhất của đồ thị

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

NGUỒN: CONTEST PRACTICE VNOI20 (WEEK 4 - T11/2019)

Cho đồ thị G n đỉnh, các đỉnh được đánh số từ 1 đến n . Ban đầu đồ thị không có cạnh nào. Cho một danh sách X gồm m cạnh, cạnh (u_i,v_i )\ ∀ i∈[1,m] nối đỉnh u_i với v_i . Bạn hãy chọn các cạnh trong danh sách X để thêm vào đồ thị G theo một thứ tự nhất định sao cho giá trị của đồ thị là lớn nhất. Giá trị của đồ thị được tính theo quy tắc:

  1. Gọi giá trị của đồ thị G valG , lúc đầu chưa có cạnh nào được đưa vào đồ thị thì valG=0
  2. Khi thêm một cạnh (u,v) vào đồ thị thì số lượng đỉnh đến được từ u và số lượng đỉnh đến được từ v trong đồ thị được cộng vào valG . Một đỉnh x được gọi là đến được từ đỉnh y nếu có đường đi từ x đến y .

Ví dụ: cho đồ thị có n=5 và danh sách X m=4 cạnh (1,2);(3,4);(4,5);(5,3)

  • Nếu thêm lần lượt các cạnh theo đúng thứ tự trong danh sách X thì giá trị của đồ thị:
    Giá trị của đồ thị là valG=22
  • Nếu thêm các cạnh của đồ thị theo thứ tự (3,4);(4,5);(1,2);(3,5) thì giá trị của đồ thị:
    Giá trị của đồ thị trong trường hợp này là valG=24 . Đây cũng là giá trị lớn nhất đồ thị nhận được.

Dữ liệu vào:

  • Dòng đầu tiên ghi 2 số nguyên dương n,m\ (1≤n≤10^5;0≤m≤2×10^5) lần lượt là số đỉnh của đồ thị G và số cạnh trong tập X
  • m dòng tiếp theo, dòng thứ i ghi 2 số nguyên dương u_i,v_i\ (1=1…m;1≤u_i,v_i≤n;u_i≠v_i) cho biết một cạch trong tập X

Dữ liệu ra:

  • Ghi ra một số nguyên duy nhất là giá trị lớn nhất của đồ thị G

Ví dụ:

Dữ liệu vào:
5 4
1 2
3 4
4 5
3 5
Dữ liệu ra:
24

Giới hạn:

  • 30\% số test tương ứng 30\% số điểm có m≤10
  • 30\% số test khác tương ứng 30\% số điểm có m cạnh tạo thành đồ thị liên thông
  • 40\% số test còn lại không có ràng buộc gì thêm.