Dưới đây là phân tích và giải pháp cho một số bài toán tiêu biểu từ kỳ thi Newcoder Multi-School 6 (2024), tập trung vào các kỹ thuật thuật toán chính.

Bài toán A: Cake

Ý tưởng giải

Đây là một bài toán kết hợp lý thuyết trò chơi đơn giản và quy hoạch động trên cây. Mục tiêu của hai người chơi được định nghĩa rõ ràng: Oscar sẽ cắt bánh để đạt được tỷ lệ số 0 lớn nhất trong tiền tố chuỗi 01 thu được, trong khi Grammy sẽ cắt để đạt được tỷ lệ số 1 lớn nhất (tức là tỷ lệ số 0 nhỏ nhất).

Chúng ta sẽ sử dụng phương pháp quy hoạch động (DP) từ dưới lên trên cây. Đối với mỗi nút u, chúng ta cần lưu trữ hai thông tin: dp_ones_count[u] là số lượng cạnh có trọng số 1 trên đường đi tối ưu trong cây con của u, và dp_path_length[u] là tổng độ dài của đường đi đó. Việc lưu trữ hai giá trị này thay vì trực tiếp lưu tỷ lệ (kiểu double) là cần thiết để có đủ thông tin khi tính toán trạng thái tiếp theo.

Trong quá trình duyệt DFS, chúng ta cũng cần truyền thông tin về đường đi từ nút gốc đến nút hiện tại u (bao gồm tổng độ dài và số lượng cạnh trọng số 1) thông qua các tham số hàm. Điều này giúp tính toán tỷ lệ tổng thể từ gốc.

Bước chuyển trạng thái là quan trọng nhất:

• Nếu nút u có độ sâu lẻ (ví dụ: 1, 3, 5...), đó là lượt của Oscar. Oscar sẽ chọn nhánh con để tối đa hóa tỷ lệ số 0 trên đường đi từ gốc đến một điểm trong nhánh con đó. Điều này tương đương với việc tối thiểu hóa tỷ lệ số 1.
• Nếu nút u có độ sâu chẵn (ví dụ: 0, 2, 4...), đó là lượt của Grammy. Grammy sẽ chọn nhánh con để tối đa hóa tỷ lệ số 1 trên đường đi từ gốc.

Khi xét một cạnh (u, v) với trọng số w, chúng ta cần so sánh hai khả năng cho đường đi từ gốc kết thúc trong cây con của v:

1. Đường đi kết thúc tại một nút tối ưu bên trong cây con của v.
2. Đường đi chỉ kết thúc tại chính nút v.

Cả hai người chơi đều sẽ chọn phương án mang lại tỷ lệ tốt nhất cho họ. Chúng ta sẽ tính tỷ lệ số 1 cho cả hai trường hợp này và lưu vào một map. Dựa vào độ sâu của u, người chơi sẽ chọn giá trị nhỏ nhất (Oscar) hoặc lớn nhất (Grammy) trong map đó.

Cuối cùng, gọi DFS từ nút gốc (ví dụ, nút 1 với độ sâu 0) để tính toán. Độ phức tạp thời gian dự kiến là O(N) hoặc O(N log N) tùy thuộc vào cài đặt của adjacency list.

Mã nguồn C++

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <iomanip>

// Sử dụng vector của map để lưu danh sách kề và trọng số cạnh
std::vector<std::map<int, int>> adjacency_list;
std::vector<int> node_depth;
std::vector<int> optimal_ones_count; // Lưu số lượng cạnh có trọng số 1 trên đường đi tối ưu
std::vector<int> optimal_path_length; // Lưu độ dài đường đi tối ưu

// Hàm DFS để tính độ sâu của các nút
void calculate_depths_dfs(int current_node, int parent_node, int current_depth) {
    node_depth[current_node] = current_depth;
    for (auto const& edge : adjacency_list[current_node]) {
        int neighbor = edge.first;
        if (neighbor == parent_node) continue;
        calculate_depths_dfs(neighbor, current_node, current_depth + 1);
    }
}

// Hàm DFS chính để giải bài toán trò chơi
void solve_game_dfs(int current_node, int parent_node, int path_len_to_root, int ones_count_to_root) {
    optimal_ones_count[current_node] = 0;
    optimal_path_length[current_node] = 0;
    
    // Map để lưu các lựa chọn (tỷ lệ 1s, {nút con, cờ chỉ ra có mở rộng cây con hay không})
    // Tỷ lệ 1s được dùng làm khóa để map tự sắp xếp
    std::map<double, std::pair<int, bool>> candidate_choices;

    for (auto const& edge : adjacency_list[current_node]) {
        int child_node = edge.first;
        int edge_weight = edge.second; // Trọng số cạnh là 0 hoặc 1
        if (child_node == parent_node) continue;

        solve_game_dfs(child_node, current_node, path_len_to_root + 1, ones_count_to_root + edge_weight);

        // Tính tỷ lệ số 1 nếu mở rộng vào cây con của child_node
        double ratio_extending_subtree = 1.0 * (optimal_ones_count[child_node] + ones_count_to_root + edge_weight) /
                                         (path_len_to_root + optimal_path_length[child_node] + 1);
        
        // Tính tỷ lệ số 1 nếu chỉ dừng lại tại child_node (chỉ lấy cạnh đến child_node)
        double ratio_stopping_at_child = 1.0 * (ones_count_to_root + edge_weight) /
                                          (path_len_to_root + 1);

        // Lưu lựa chọn có tỷ lệ số 1 nhỏ hơn vào map (Oscar muốn tối đa 0s -> tối thiểu 1s)
        if (ratio_extending_subtree < ratio_stopping_at_child) {
            candidate_choices[ratio_extending_subtree] = {child_node, true}; // true: mở rộng cây con
        } else {
            candidate_choices[ratio_stopping_at_child] = {child_node, false}; // false: dừng tại child_node
        }
    }

    if (candidate_choices.empty()) { // Nếu là lá
        return;
    }

    std::pair<int, bool> best_choice_data;
    if (node_depth[current_node] % 2 == 1) { // Oscar chọn (độ sâu lẻ), muốn tối đa 0s => tối thiểu 1s
        best_choice_data = candidate_choices.begin()->second;
    } else { // Grammy chọn (độ sâu chẵn), muốn tối đa 1s
        best_choice_data = candidate_choices.rbegin()->second;
    }

    int chosen_child = best_choice_data.first;
    bool extend_subtree = best_choice_data.second;

    int edge_weight_to_child = adjacency_list[current_node][chosen_child];

    if (extend_subtree) {
        optimal_ones_count[current_node] = optimal_ones_count[chosen_child] + edge_weight_to_child;
        optimal_path_length[current_node] = optimal_path_length[chosen_child] + 1;
    } else {
        optimal_ones_count[current_node] = edge_weight_to_child;
        optimal_path_length[current_node] = 1;
    }
}

void solve_test_case() {
    int n_nodes;
    std::cin >> n_nodes;

    adjacency_list.assign(n_nodes + 1, std::map<int, int>());
    node_depth.assign(n_nodes + 1, 0);
    optimal_ones_count.assign(n_nodes + 1, 0);
    optimal_path_length.assign(n_nodes + 1, 0);

    for (int i = 0; i < n_nodes - 1; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        adjacency_list[u][v] = w;
        adjacency_list[v][u] = w;
    }

    calculate_depths_dfs(1, 0, 0); // Tính độ sâu từ gốc 1
    solve_game_dfs(1, 0, 0, 0); // Bắt đầu giải DP từ gốc 1, với đường đi đến gốc (parent_node) có độ dài 0 và 0 số 1

    double final_answer = 1.0 * optimal_ones_count[1] / optimal_path_length[1];
    std::cout << final_answer << std::endl;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    std::cout << std::fixed << std::setprecision(11);

    int num_test_cases;
    std::cin >> num_test_cases;
    while (num_test_cases--) {
        solve_test_case();
    }
    return 0;
}

Bài toán D: Puzzle: Wagiri

Ý tưởng giải

Bài toán này liên quan đến lý thuyết đồ thị và các thành phần liên thông. Nó yêu cầu chúng ta xác định một tập hợp các cạnh sao cho đồ thị cuối cùng là liên thông, chỉ sử dụng các cạnh ban đầu, đồng thời tuân thủ một số điều kiện về "cạnh bánh xe" và "cạnh cắt".

Bước 1: Loại bỏ cạnh không cần thiết. Đầu tiên, chúng ta chỉ quan tâm đến các cạnh bánh xe (lun) mà nằm trong ít nhất một chu trình. Các cạnh bánh xe không nằm trong chu trình (tức là cầu) sẽ không bao giờ thỏa mãn điều kiện và có thể bị loại bỏ ngay lập tức. Để xác định các cạnh này, chúng ta có thể sử dụng thuật toán Tarjan để tìm các thành phần song liên thông đỉnh (vDCCs).

Bước 2: Co rút đồ thị. Sau khi xác định các vDCC, chúng ta sẽ "co rút" mỗi vDCC thành một đỉnh duy nhất. Điều này tạo ra một đồ thị mới chỉ bao gồm các đỉnh đại diện cho các vDCC và các đỉnh là điểm cắt.

Bước 3: Nối các thành phần bằng cạnh cắt. Tiếp theo, chúng ta sẽ xem xét các cạnh cắt (qie) còn lại. Chúng ta muốn sử dụng càng ít cạnh cắt càng tốt để nối các thành phần đã co rút và các điểm cắt thành một đồ thị liên thông duy nhất. Điều này có thể được thực hiện bằng cách sử dụng một cấu trúc dữ liệu Disjoint Set Union (DSU). Khởi tạo DSU với mỗi đỉnh ban đầu là một tập hợp riêng biệt. Sau đó, cho mỗi vDCC có kích thước lớn hơn 1 (tức là các nút trong vDCC đó đều thuộc cùng một thành phần liên thông), hợp nhất tất cả các đỉnh trong vDCC đó vào cùng một tập hợp DSU.

Sau đó, duyệt qua các cạnh cắt: nếu một cạnh nối hai đỉnh thuộc hai tập hợp DSU khác nhau, thì cạnh đó có thể được thêm vào để nối hai thành phần. Chúng ta hợp nhất hai tập hợp này trong DSU. Đồng thời, chúng ta lưu lại tất cả các cạnh đã chọn. Các cạnh bánh xe được giữ lại là những cạnh nối hai đỉnh thuộc cùng một thành phần DSU ban đầu (tức là chúng nằm trong cùng một vDCC lớn hơn 1).

Bước 4: Kiểm tra tính liên thông cuối cùng. Cuối cùng, sau khi đã xử lý tất cả các cạnh, chúng ta kiểm tra xem tất cả các đỉnh của đồ thị ban đầu có thuộc cùng một thành phần liên thông trong DSU hay không. Nếu có, chúng ta in ra "YES" và danh sách các cạnh đã chọn. Ngược lại, in ra "NO".

Độ phức tạp thời gian của giải pháp này là O(N + M) do sử dụng Tarjan và DSU.

Mã nguồn C++

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <map>

const int MAX_NODES = 1e5 + 7;

std::vector<std::pair<int, int>> wheel_edges_list, cut_edges_list;
std::vector<int> adj_graph[MAX_NODES]; // Danh sách kề cho Tarjan

// Các biến cho thuật toán Tarjan
int discovery_time[MAX_NODES], low_link_time[MAX_NODES], timer_counter;
std::stack<int> node_stack;
bool is_articulation_point[MAX_NODES]; // Kiểm tra xem một nút có phải điểm cắt hay không
std::vector<int> biconnected_components[MAX_NODES]; // Các thành phần song liên thông đỉnh (vDCCs)
int dcc_count; // Số lượng vDCCs
int tarjan_root; // Nút gốc hiện tại cho DFS của Tarjan

// Hàm Tarjan để tìm vDCCs
void tarjan_dfs(int u_node) {
    discovery_time[u_node] = low_link_time[u_node] = ++timer_counter;
    node_stack.push(u_node);

    if (adj_graph[u_node].empty() && u_node == tarjan_root) { // Xử lý trường hợp nút cô lập
        biconnected_components[++dcc_count].push_back(u_node);
        return;
    }

    int child_count = 0;
    for (int v_neighbor : adj_graph[u_node]) {
        if (!discovery_time[v_neighbor]) { // Nếu v_neighbor chưa được thăm
            tarjan_dfs(v_neighbor);
            low_link_time[u_node] = std::min(low_link_time[u_node], low_link_time[v_neighbor]);
            if (low_link_time[v_neighbor] >= discovery_time[u_node]) {
                child_count++;
                if (u_node != tarjan_root || child_count > 1) {
                    is_articulation_point[u_node] = true;
                }
                dcc_count++;
                int stack_node;
                do { // Ghi nhận vDCC
                    stack_node = node_stack.top();
                    node_stack.pop();
                    biconnected_components[dcc_count].push_back(stack_node);
                } while (stack_node != v_neighbor);
                biconnected_components[dcc_count].push_back(u_node);
            }
        } else {
            low_link_time[u_node] = std::min(low_link_time[u_node], discovery_time[v_neighbor]);
        }
    }
}

// Cấu trúc DSU (Disjoint Set Union)
int dsu_parent[MAX_NODES];
void dsu_init(int n) {
    for (int i = 0; i <= n; ++i) {
        dsu_parent[i] = i;
    }
}
int dsu_find(int i) {
    if (dsu_parent[i] == i) return i;
    return dsu_parent[i] = dsu_find(dsu_parent[i]);
}
void dsu_unite(int i, int j) {
    int root_i = dsu_find(i);
    int root_j = dsu_find(j);
    if (root_i != root_j) {
        dsu_parent[root_i] = root_j;
    }
}

void solve_test_case() {
    int n_nodes, m_edges;
    std::cin >> n_nodes >> m_edges;

    // Reset global variables for each test case
    wheel_edges_list.clear();
    cut_edges_list.clear();
    for (int i = 1; i <= n_nodes; ++i) {
        adj_graph[i].clear();
        discovery_time[i] = 0;
        low_link_time[i] = 0;
        is_articulation_point[i] = false;
        biconnected_components[i].clear();
    }
    timer_counter = 0;
    dcc_count = 0;
    while (!node_stack.empty()) node_stack.pop();

    for (int i = 0; i < m_edges; ++i) {
        int u, v;
        std::string edge_type_str;
        std::cin >> u >> v >> edge_type_str;
        if (edge_type_str[0] == 'L') { // Cạnh bánh xe (Wheel edge)
            wheel_edges_list.push_back({u, v});
            adj_graph[u].push_back(v);
            adj_graph[v].push_back(u);
        } else { // Cạnh cắt (Cut edge)
            cut_edges_list.push_back({u, v});
        }
    }

    // Chạy Tarjan cho từng thành phần liên thông
    for (tarjan_root = 1; tarjan_root <= n_nodes; ++tarjan_root) {
        if (!discovery_time[tarjan_root]) {
            tarjan_dfs(tarjan_root);
        }
    }

    dsu_init(n_nodes);
    std::vector<std::pair<int, int>> final_selected_edges;

    // Gộp các nút trong cùng một vDCC thành một thành phần DSU nếu vDCC có >= 2 nút
    // (VDCC với 1 nút có thể là nút cô lập hoặc là nút lá/treo)
    for (int i = 1; i <= dcc_count; ++i) {
        if (biconnected_components[i].size() >= 2) { // Một vDCC thực sự
            for (size_t k = 1; k < biconnected_components[i].size(); ++k) {
                dsu_unite(biconnected_components[i][0], biconnected_components[i][k]);
            }
        }
    }

    // Thêm các cạnh bánh xe nếu chúng liên thông các thành phần đã được gộp
    for (auto const& edge_pair : wheel_edges_list) {
        int u = edge_pair.first;
        int v = edge_pair.second;
        // Chỉ thêm cạnh bánh xe nếu u và v đã thuộc cùng một DSU sau khi co rút vDCC
        // (Điều này có nghĩa là chúng nằm trong cùng một vDCC ban đầu hoặc được nối bởi một vDCC)
        if (dsu_find(u) == dsu_find(v)) {
            final_selected_edges.push_back(edge_pair);
        }
    }

    // Thêm các cạnh cắt để nối các thành phần còn lại
    for (auto const& edge_pair : cut_edges_list) {
        int u = edge_pair.first;
        int v = edge_pair.second;
        if (dsu_find(u) != dsu_find(v)) { // Nếu u và v chưa liên thông
            dsu_unite(u, v); // Hợp nhất chúng
            final_selected_edges.push_back(edge_pair);
        }
    }

    // Kiểm tra xem tất cả các nút có liên thông hay không
    bool all_connected = true;
    if (n_nodes > 0) { // Đồ thị không rỗng
        int root_of_first_node = dsu_find(1);
        for (int i = 2; i <= n_nodes; ++i) {
            if (dsu_find(i) != root_of_first_node) {
                all_connected = false;
                break;
            }
        }
    } else { // Đồ thị rỗng được coi là liên thông
        all_connected = true;
    }


    if (all_connected) {
        std::cout << "YES\n";
        std::cout << final_selected_edges.size() << "\n";
        for (auto const& edge : final_selected_edges) {
            std::cout << edge.first << " " << edge.second << "\n";
        }
    } else {
        std::cout << "NO\n";
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    // Bài toán này chỉ có 1 test case
    solve_test_case();
    return 0;
}

Bài toán F: Challenge NPC 2

Ý tưởng giải

Bài toán này yêu cầu chúng ta sắp xếp các đỉnh của một đồ thị thành một dãy để thỏa mãn một điều kiện nhất định, hoặc xác định rằng không có giải pháp. Điều kiện chính là không có hai đỉnh kề nhau trong đồ thị ban đầu lại đứng cạnh nhau trong dãy kết quả.

Điều kiện không có giải pháp: Nếu đồ thị đầu vào là một đồ thị hình sao (star graph), tức là có một đỉnh trung tâm nối với tất cả N-1 đỉnh còn lại. Trong trường hợp này, đỉnh trung tâm sẽ luôn phải đứng cạnh ít nhất hai đỉnh khác trong dãy, và vì nó kề với tất cả các đỉnh khác, chắc chắn sẽ có một cặp kề nhau vi phạm điều kiện. Do đó, nếu tồn tại một đỉnh có bậc N-1, không có giải pháp.

Trường hợp đặc biệt N=3: Với N=3, có 3 đỉnh. Nếu không có cạnh nào (đồ thị rỗng), output 1 2 3. Nếu có một cạnh, ví dụ (1,2), output 1 3 2 (đỉnh 3 xen vào giữa). Nếu có hai cạnh, ví dụ (1,2) và (1,3), output 1 2 3. Nếu có ba cạnh (đồ thị K3), output -1 vì luôn có đỉnh kề nhau.

Giải pháp cho N >= 4 (và không phải đồ thị hình sao): Nếu đồ thị không phải là đồ thị hình sao và N >= 4, luôn tồn tại một giải pháp. Ý tưởng là xây dựng một đường đi dài nhất (đường kính của cây) và sau đó phân chia các đỉnh vào hai tập hợp xen kẽ:

1. Nối các thành phần liên thông: Nếu đồ thị có nhiều thành phần liên thông (là một rừng), chúng ta có thể nối chúng lại để tạo thành một cây duy nhất. Cách nối là tìm đường kính của mỗi cây con, sau đó nối một đầu của đường kính này với một đầu của đường kính của cây con tiếp theo. Việc này tạo ra một cây lớn mà đường kính của nó sẽ đủ dài (ít nhất là 4 đối với N>=4, không phải hình sao).
2. Phân tầng BFS: Sau khi có một cây lớn, chúng ta thực hiện BFS bắt đầu từ một đầu của đường kính (hoặc bất kỳ nút nào). Các đỉnh sẽ được phân vào hai tầng luân phiên: tầng 1 (layer1_nodes) và tầng 2 (layer2_nodes). Tất cả các đỉnh trong layer1_nodes sẽ không kề nhau với bất kỳ đỉnh nào trong cùng layer1_nodes, và tương tự cho layer2_nodes. Các đỉnh kề nhau sẽ luôn nằm ở các tầng khác nhau.
3. In kết quả: Để đảm bảo không có hai đỉnh kề nhau xuất hiện liên tiếp trong dãy, chúng ta in tất cả các đỉnh trong layer2_nodes trước, sau đó in tất cả các đỉnh trong layer1_nodes. Thứ tự này giúp xử lý hiệu quả các trường hợp N nhỏ (như N=4), nơi các đỉnh từ hai tầng có thể kề nhau.

Độ phức tạp thời gian của giải pháp này là O(N + M).

Mã nguồn C++

#include <iostream>
#include <vector>
#include <numeric> // for std::iota
#include <algorithm>
#include <set>
#include <queue>

const int MAX_NODES = 5e5 + 7;

std::vector<int> adj_graph_challenge[MAX_NODES]; // Danh sách kề của đồ thị
int node_degree[MAX_NODES]; // Bậc của mỗi nút

// DSU (Disjoint Set Union) để tìm các thành phần liên thông
int dsu_parent[MAX_NODES];
void dsu_initialize(int n) {
    std::iota(dsu_parent + 1, dsu_parent + n + 1, 1);
}
int dsu_find(int i) {
    if (dsu_parent[i] == i) return i;
    return dsu_parent[i] = dsu_find(dsu_parent[i]);
}
void dsu_unite(int i, int j) {
    int root_i = dsu_find(i);
    int root_j = dsu_find(j);
    if (root_i != root_j) {
        dsu_parent[root_i] = root_j;
    }
}

// Các biến và hàm cho việc tìm đường kính và BFS phân tầng
bool visited_bfs[MAX_NODES];
std::vector<int> layer1_nodes, layer2_nodes; // Các tầng nút để in ra
int max_dfs_depth, farthest_node_in_component;

// DFS để tìm nút xa nhất từ một điểm bất kỳ (dùng để tìm đường kính)
void find_farthest_dfs(int u, int parent, int current_depth) {
    if (current_depth > max_dfs_depth) {
        max_dfs_depth = current_depth;
        farthest_node_in_component = u;
    }
    for (int v : adj_graph_challenge[u]) {
        if (v == parent) continue;
        find_farthest_dfs(v, u, current_depth + 1);
    }
}

// BFS để phân tầng các nút
void perform_bfs_layering(int start_node) {
    std::queue<int> q_even_layer, q_odd_layer;
    q_even_layer.push(start_node); // Bắt đầu từ tầng 0 (chẵn)
    
    // Đảm bảo tất cả visited được reset
    for(int i = 0; i < MAX_NODES; ++i) visited_bfs[i] = false;

    while (!q_even_layer.empty() || !q_odd_layer.empty()) {
        // Xử lý tầng chẵn
        while (!q_even_layer.empty()) {
            int u = q_even_layer.front();
            q_even_layer.pop();
            if (visited_bfs[u]) continue;
            visited_bfs[u] = true;
            layer1_nodes.push_back(u); // Tầng này sẽ là layer1_nodes

            for (int v : adj_graph_challenge[u]) {
                if (!visited_bfs[v]) {
                    q_odd_layer.push(v); // Chuyển sang tầng lẻ
                }
            }
        }
        // Xử lý tầng lẻ
        while (!q_odd_layer.empty()) {
            int u = q_odd_layer.front();
            q_odd_layer.pop();
            if (visited_bfs[u]) continue;
            visited_bfs[u] = true;
            layer2_nodes.push_back(u); // Tầng này sẽ là layer2_nodes

            for (int v : adj_graph_challenge[u]) {
                if (!visited_bfs[v]) {
                    q_even_layer.push(v); // Chuyển sang tầng chẵn
                }
            }
        }
    }
}

// Set để kiểm tra cạnh cho N=3
std::set<std::pair<int, int>> existing_edges_set;

void solve_test_case() {
    int n_nodes, m_edges;
    std::cin >> n_nodes >> m_edges;

    // Reset các cấu trúc dữ liệu cho mỗi test case
    dsu_initialize(n_nodes);
    layer1_nodes.clear();
    layer2_nodes.clear();
    existing_edges_set.clear();

    for (int i = 1; i <= n_nodes; ++i) {
        node_degree[i] = 0;
        adj_graph_challenge[i].clear();
        visited_bfs[i] = false; // Reset visited_bfs here
    }

    for (int i = 0; i < m_edges; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj_graph_challenge[u].push_back(v);
        adj_graph_challenge[v].push_back(u);
        existing_edges_set.insert({std::min(u, v), std::max(u, v)}); // Để kiểm tra cạnh cho N=3
        dsu_unite(u, v);
        node_degree[u]++;
        node_degree[v]++;
    }

    // Kiểm tra trường hợp đồ thị hình sao (star graph)
    for (int i = 1; i <= n_nodes; ++i) {
        if (node_degree[i] == n_nodes - 1) {
            std::cout << -1 << "\n";
            return;
        }
    }

    // Xử lý trường hợp đặc biệt N=3
    if (n_nodes == 3) {
        // Kiểm tra các cạnh và in ra thứ tự phù hợp
        if (!existing_edges_set.count({1, 2})) std::cout << "1 3 2\n"; // 1-3-2 nếu (1,2) không có
        else if (!existing_edges_set.count({1, 3})) std::cout << "1 2 3\n"; // 1-2-3 nếu (1,3) không có
        else if (!existing_edges_set.count({2, 3})) std::cout << "2 1 3\n"; // 2-1-3 nếu (2,3) không có
        else std::cout << "1 2 3\n"; // K3, không có giải pháp theo mô tả nhưng đã bị loại bởi star graph check?
                                    // Thực ra K3 cũng là trường hợp vô nghiệm cho N=3
                                    // Tuy nhiên, bài toán này có vẻ cho phép K3 nếu không có đỉnh bậc N-1,
                                    // nhưng K3 (m=3) có 3 đỉnh bậc 2, không có đỉnh bậc N-1 (2).
                                    // Nếu K3 vô nghiệm thì output -1, nhưng test case có thể mong đợi 1 2 3.
                                    // Dựa theo mã gốc, N=3 K3 in 1 2 3. Điều này có vẻ mâu thuẫn.
                                    // Nếu N=3 và m=3, đồ thị là K3 (complete graph), thì mọi đỉnh đều kề với mọi đỉnh khác.
                                    // Sẽ không thể sắp xếp 1 2 3 mà không có đỉnh kề nhau.
                                    // Giả định rằng nếu K3 (N=3, m=3) thì nó đã bị loại bởi check bậc N-1.
                                    // Bậc của mỗi nút trong K3 N=3 là 2, N-1 = 2.
                                    // Vậy K3 N=3 lẽ ra phải ra -1.
                                    // Mã gốc có vẻ có lỗi ở chỗ này, hoặc có một luật chơi ngầm khác.
                                    // Để giữ đúng theo mã gốc, tôi sẽ giữ 1 2 3 ở đây.
                                    // Tuy nhiên, nếu N=3, m=3, output 1 2 3, thì (1,2) kề, (2,3) kề. Chỉ (1,3) không kề (mặc định)
                                    // Nhưng trong K3, (1,3) cũng kề. Vậy 1 2 3 là sai.
                                    // Tôi sẽ làm theo logic đúng: K3 N=3 vô nghiệm.
        // Cần kiểm tra lại: N=3 và m=3 (K3) thì node_degree[i] == 2 == N-1.
        // Vậy nó sẽ bị bắt bởi `node_degree[i] == n_nodes - 1` và in -1.
        // Do đó, nếu đến đoạn N=3 này, m chắc chắn < 3.
        // Vậy các trường hợp trên là đúng. (0, 1 hoặc 2 cạnh).
        // Ví dụ: N=3, m=0 -> 1 2 3
        // Ví dụ: N=3, m=1 (1-2) -> 1 3 2
        // Ví dụ: N=3, m=2 (1-2, 1-3) -> 1 2 3
        // Ví dụ: N=3, m=2 (1-2, 2-3) -> 2 1 3
        return;
    }

    // Xử lý các thành phần liên thông
    int last_endpoint_of_diameter = -1; // Lưu điểm cuối của đường kính cây trước đó
    std::set<int> roots_of_components;
    for (int i = 1; i <= n_nodes; ++i) {
        roots_of_components.insert(dsu_find(i));
    }

    for (int root_comp : roots_of_components) {
        // Tìm một nút bất kỳ trong thành phần liên thông
        int start_node_in_comp = -1;
        for(int i = 1; i <= n_nodes; ++i) {
            if (dsu_find(i) == root_comp) {
                start_node_in_comp = i;
                break;
            }
        }
        if (start_node_in_comp == -1) continue; // Không tìm thấy nút nào (có thể thành phần rỗng nếu N=0)

        // Tìm một đầu của đường kính
        max_dfs_depth = 0;
        farthest_node_in_component = start_node_in_comp;
        find_farthest_dfs(farthest_node_in_component, 0, 0); 
        int one_end_of_diameter = farthest_node_in_component;

        // Tìm đầu kia của đường kính
        max_dfs_depth = 0;
        farthest_node_in_component = one_end_of_diameter;
        find_farthest_dfs(farthest_node_in_component, 0, 0); 
        int other_end_of_diameter = farthest_node_in_component;

        // Nối các đường kính của các cây lại với nhau
        if (last_endpoint_of_diameter != -1) {
            adj_graph_challenge[other_end_of_diameter].push_back(last_endpoint_of_diameter);
            adj_graph_challenge[last_endpoint_of_diameter].push_back(other_end_of_diameter);
        }
        last_endpoint_of_diameter = one_end_of_diameter; // Lưu lại để nối với cây tiếp theo
    }
    
    // Sau khi nối tất cả các cây, đồ thị bây giờ là một cây lớn.
    // Thực hiện BFS phân tầng từ một đầu của đường kính của cây lớn này
    max_dfs_depth = 0;
    farthest_node_in_component = last_endpoint_of_diameter;
    find_farthest_dfs(farthest_node_in_component, 0, 0); // Tìm một đầu của đường kính của cây lớn
    
    perform_bfs_layering(farthest_node_in_component);

    // In ra layer2_nodes trước, sau đó là layer1_nodes
    // Điều này đảm bảo không có hai đỉnh kề nhau xuất hiện liên tiếp
    for (int node : layer2_nodes) {
        std::cout << node << " ";
    }
    for (int node : layer1_nodes) {
        std::cout << node << " ";
    }
    std::cout << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t_cases;
    std::cin >> t_cases;
    while (t_cases--) {
        solve_test_case();
    }
    return 0;
}

Bài toán I: Intersecting Intervals

Ý tưởng giải

Bài toán này yêu cầu tìm tổng lớn nhất của các đoạn con, với điều kiện các đoạn con trên các hàng liên tiếp phải "cắt nhau" (có ít nhất một cột chung). Đây là một bài toán quy hoạch động (DP).

Chúng ta định nghĩa dp_table[i][j] là tổng lớn nhất có thể đạt được từ hàng 1 đến hàng i, với điều kiện đoạn con ở hàng i phải chứa (hoặc kết thúc/bắt đầu tại) phần tử ở cột j.

Để tính toán dp_table[i][j], chúng ta cần xem xét tất cả các khả năng cho vị trí kết thúc k của đoạn con ở hàng i-1. Có hai trường hợp chính:

1. Đoạn con ở hàng i-1 kết thúc tại cột k <= j:

   Trong trường hợp này, đoạn con ở hàng i-1 kéo dài từ một điểm nào đó đến cột k. Đoạn con ở hàng i phải chứa cột j và cắt đoạn con ở hàng i-1 (tại cột k). Công thức chuyển trạng thái sẽ là: dp_table[i-1][k] + (prefix_sum[i][j] - prefix_sum[i][k-1]) + max_ending_sum[i][k-1] + max_starting_sum[i][j+1] Giải thích:

   • dp_table[i-1][k]: Giá trị tối ưu đến hàng i-1, kết thúc tại k.
   • (prefix_sum[i][j] - prefix_sum[i][k-1]): Tổng các phần tử từ cột k đến j ở hàng i. Đây là phần chung của hai đoạn con.
   • max_ending_sum[i][k-1]: Tổng đoạn con lớn nhất kết thúc tại k-1 ở hàng i (có thể là 0, nếu bắt đầu từ k là tốt hơn).
   • max_starting_sum[i][j+1]: Tổng đoạn con lớn nhất bắt đầu tại j+1 ở hàng i (có thể là 0, nếu kết thúc tại j là tốt hơn).

2. Đoạn con ở hàng i-1 kết thúc tại cột k > j:

   Tương tự như trên, nhưng đoạn con ở hàng i-1 kết thúc sau cột j. Công thức chuyển trạng thái sẽ là: dp_table[i-1][k] + (prefix_sum[i][k] - prefix_sum[i][j-1]) + max_ending_sum[i][j-1] + max_starting_sum[i][k+1]

Các mảng phụ trợ: Để tính toán các công thức trên, chúng ta cần ba mảng phụ trợ cho mỗi hàng i:

• max_ending_sum[i][j]: tổng đoạn con lớn nhất kết thúc tại cột j ở hàng i (có thể là 0 nếu tất cả các tổng đều âm).
• max_starting_sum[i][j]: tổng đoạn con lớn nhất bắt đầu tại cột j ở hàng i (có thể là 0).
• prefix_sum[i][j]: tổng tiền tố của các phần tử từ cột 1 đến j ở hàng i.

Các mảng này có thể được tính trong O(M) cho mỗi hàng.

Tối ưu hóa từ O(N*M^2) xuống O(N*M): Nếu tính toán dp_table[i][j] bằng cách duyệt qua tất cả k, độ phức tạp sẽ là O(N * M * M) = O(N*M^2). Chúng ta có thể tối ưu bằng cách quan sát công thức chuyển trạng thái:

Khi k <= j, biểu thức có thể viết lại thành: (dp_table[i-1][k] - prefix_sum[i][k-1] + max_ending_sum[i][k-1]) + prefix_sum[i][j] + max_starting_sum[i][j+1] Phần trong ngoặc đơn chỉ phụ thuộc vào k. Phần còn lại chỉ phụ thuộc vào j. Chúng ta có thể tính trước giá trị lớn nhất của phần trong ngoặc đơn cho mọi k <= j bằng một mảng tiền tố tối đa (max_val_left[i][j]).

Khi k > j, biểu thức có thể viết lại thành: (dp_table[i-1][k] + prefix_sum[i][k] + max_starting_sum[i][k+1]) - prefix_sum[i][j-1] + max_ending_sum[i][j-1] Tương tự, phần trong ngoặc đơn chỉ phụ thuộc vào k. Phần còn lại chỉ phụ thuộc vào j. Chúng ta có thể tính trước giá trị lớn nhất của phần trong ngoặc đơn cho mọi k > j bằng một mảng hậu tố tối đa (max_val_right[i][j]).

Bằng cách này, mỗi dp_table[i][j] có thể được tính trong O(1) sau khi các mảng tiền tố/hậu tố tối đa được tính, giảm tổng độ phức tạp xuống O(N*M).

Kết quả cuối cùng là giá trị lớn nhất trong dp_table[n][j] cho tất cả j.

Mã nguồn C++

#include <iostream>
#include <vector>
#include <algorithm>

// Sử dụng namespace std;
// #define endl '\n'
// #define IOS std::ios::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0)

void solve_test_case() {
    int n_rows, m_cols;
    std::cin >> n_rows >> m_cols;

    // matrix_vals[i][j] lưu giá trị tại hàng i, cột j
    std::vector<std::vector<long long>> matrix_vals(n_rows + 2, std::vector<long long>(m_cols + 2, 0));
    for (int i = 1; i <= n_rows; ++i) {
        for (int j = 1; j <= m_cols; ++j) {
            std::cin >> matrix_vals[i][j];
        }
    }

    // max_ending_sum[i][j]: tổng đoạn con lớn nhất kết thúc tại j ở hàng i (>= 0)
    std::vector<std::vector<long long>> max_ending_sum(n_rows + 2, std::vector<long long>(m_cols + 2, 0));
    // max_starting_sum[i][j]: tổng đoạn con lớn nhất bắt đầu tại j ở hàng i (>= 0)
    std::vector<std::vector<long long>> max_starting_sum(n_rows + 2, std::vector<long long>(m_cols + 2, 0));
    // row_prefix_sum[i][j]: tổng tiền tố đến j ở hàng i
    std::vector<std::vector<long long>> row_prefix_sum(n_rows + 2, std::vector<long long>(m_cols + 2, 0));
    
    // dp_table[i][j]: giá trị tối ưu đến hàng i, bắt buộc chọn phần tử j ở hàng i
    std::vector<std::vector<long long>> dp_table(n_rows + 2, std::vector<long long>(m_cols + 2, 0));

    // Tính toán max_ending_sum, max_starting_sum và row_prefix_sum cho mỗi hàng
    for (int i = 1; i <= n_rows; ++i) {
        for (int j = 1; j <= m_cols; ++j) {
            max_ending_sum[i][j] = std::max({max_ending_sum[i][j-1] + matrix_vals[i][j], matrix_vals[i][j], 0LL});
            row_prefix_sum[i][j] = row_prefix_sum[i][j-1] + matrix_vals[i][j];
        }
        for (int j = m_cols; j >= 1; --j) {
            max_starting_sum[i][j] = std::max({max_starting_sum[i][j+1] + matrix_vals[i][j], matrix_vals[i][j], 0LL});
        }
    }
    
    // Mảng phụ trợ cho tối ưu hóa DP (prefix/suffix max)
    // max_left_term[i][j]: max của (dp_table[i-1][k] - row_prefix_sum[i][k-1] + max_ending_sum[i][k-1]) cho k <= j
    std::vector<std::vector<long long>> max_left_term(n_rows + 2, std::vector<long long>(m_cols + 2, -4e18)); // Giá trị âm vô cùng
    // max_right_term[i][j]: max của (dp_table[i-1][k] + row_prefix_sum[i][k] + max_starting_sum[i][k+1]) cho k >= j
    std::vector<std::vector<long long>> max_right_term(n_rows + 2, std::vector<long long>(m_cols + 2, -4e18));

    // Tính toán DP
    for (int i = 1; i <= n_rows; ++i) {
        // Khởi tạo các giá trị đầu tiên cho max_left_term và max_right_term
        // Giá trị tại cột 1
        max_left_term[i][1] = dp_table[i-1][1] - row_prefix_sum[i][0] + max_ending_sum[i][0]; // k=1, k-1=0
        // Giá trị tại cột m_cols
        max_right_term[i][m_cols] = dp_table[i-1][m_cols] + row_prefix_sum[i][m_cols] + max_starting_sum[i][m_cols+1];

        // Tính max_left_term từ trái sang phải
        for (int j = 2; j <= m_cols; ++j) {
            long long current_k_term = dp_table[i-1][j] - row_prefix_sum[i][j-1] + max_ending_sum[i][j-1];
            max_left_term[i][j] = std::max(max_left_term[i][j-1], current_k_term);
        }
        // Tính max_right_term từ phải sang trái
        for (int j = m_cols - 1; j >= 1; --j) {
            long long current_k_term = dp_table[i-1][j] + row_prefix_sum[i][j] + max_starting_sum[i][j+1];
            max_right_term[i][j] = std::max(max_right_term[i][j+1], current_k_term);
        }

        // Tính dp_table[i][j] sử dụng các mảng tối ưu hóa
        for (int j = 1; j <= m_cols; ++j) {
            long long val1 = max_left_term[i][j] + row_prefix_sum[i][j] + max_starting_sum[i][j+1];
            long long val2 = max_right_term[i][j] - row_prefix_sum[i][j-1] + max_ending_sum[i][j-1];
            dp_table[i][j] = std::max(val1, val2);
        }
    }

    // Tìm kết quả cuối cùng là giá trị lớn nhất trong hàng cuối cùng của dp_table
    long long final_ans = -4e18; // Giá trị âm vô cùng
    for (int j = 1; j <= m_cols; ++j) {
        final_ans = std::max(final_ans, dp_table[n_rows][j]);
    }
    std::cout << final_ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t_cases;
    std::cin >> t_cases;
    while (t_cases--) {
        solve_test_case();
    }
    return 0;
}