NGUỒN: CONTEST PRACTICE VNOI20 (WEEK 4 - T11/2019)
Cho đồ thị có đỉnh, các đỉnh được đánh số từ đến . Ban đầu đồ thị không có cạnh nào. Cho một danh sách gồm cạnh, cạnh nối đỉnh với . Bạn hãy chọn các cạnh trong danh sách để thêm vào đồ thị 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:
Gọi giá trị của đồ thị là , lúc đầu chưa có cạnh nào được đưa vào đồ thị thì
Khi thêm một cạnh vào đồ thị thì số lượng đỉnh đến được từ và số lượng đỉnh đến được từ trong đồ thị được cộng vào . Một đỉnh được gọi là đến được từ đỉnh nếu có đường đi từ đến .
Ví dụ: cho đồ thị có và danh sách có cạnh
Nếu thêm lần lượt các cạnh theo đúng thứ tự trong danh sách thì giá trị của đồ thị:
Giá trị của đồ thị là
Nếu thêm các cạnh của đồ thị theo thứ tự thì giá trị của đồ thị:
Giá trị của đồ thị trong trường hợp này là . Đâ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 số nguyên dương lần lượt là số đỉnh của đồ thị và số cạnh trong tập
dòng tiếp theo, dòng thứ ghi số nguyên dương cho biết một cạch trong tập
Dữ liệu ra:
Ghi ra một số nguyên duy nhất là giá trị lớn nhất của đồ thị
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:
số test tương ứng số điểm có
số test khác tương ứng số điểm có cạnh tạo thành đồ thị liên thông
