Codechef DRGHTS问题实现逻辑错误排查请求

问题背景 #

疗养院包含N个房间与M条通道，任意两房间间最多存在一条通行路径（即图为森林）。部分房间的窗户处于开启状态：

• 若两个不同房间均开窗且彼此连通，则两者间存在穿堂风。
• Furik需要统计存在穿堂风的房间对数量。
• Rubik需要统计至少有一条穿堂风经过的房间数量（即位于任意两个开窗连通房间路径上的房间）。

输入格式：

1. 第一行输入两个整数N和M；
2. 第二行输入N个整数，第i个数为1表示第i个房间开窗，为0则相反；
3. 接下来M行每行输入一对整数，表示相连的两个房间（房间编号为1到N）。

用户提交的代码 #

class DisjointSet {
public: 
    vector<int> dsize, parent, closed;
    DisjointSet(int n) {
        dsize.resize(n+1, 1);
        closed.resize(n+1);
        parent.resize(n+1);
        for (int i = 1; i <= n; i++) parent[i] = i;
    }

    int findParent(int u) {
        if (parent[u] == u) return u;
       return parent[u] = findParent(parent[u]);
    }

    void unionBySize(int u, int v) {
        int pu = findParent(u), pv = findParent(v);
        if (pu == pv) return;
    
        if (dsize[pu] < dsize[pv]) {
            parent[pu] = pv;
            dsize[pv] += dsize[pu];
            closed[pv] += closed[pu];
        } else {
            parent[pv] = pu;
            dsize[pu] += dsize[pv];
            closed[pu] += closed[pv];
        }
    }
};

pair<int, int> solve(int n, DisjointSet &dset, vector<int> &windows) {
    int pairs = 0, rooms = 0;
    for (int i = 1; i <= n; i++) {
        if (dset.findParent(i) == i) {
            int openWindows = dset.dsize[i] - dset.closed[i];
            if (openWindows > 1) {
                rooms += openWindows;
                pairs += (openWindows * (openWindows - 1)) / 2;
            }
        }
    }
    return {pairs, rooms};
}

int main() {
    int N, M;
    cin >> N >> M;
    DisjointSet dset(N);
    vector<int> windows(N+1);
    for (int i = 1; i <= N; i++) {
        cin >> windows[i];
        if (windows[i] == 0) dset.closed[i]++;
    }
    while (M--) {
        int u, v;
        cin >> u >> v;
        dset.unionBySize(v, u);
    }
    pair<int, int> ans = solve(N, dset, windows);
    cout << ans.first << " " << ans.second << endl;
    return 0;
}

逻辑错误分析 #

1. Rubik的答案计算完全错误 #

代码中rooms的计算逻辑是：当连通块内开窗房间数≥2时，仅将开窗房间数计入结果。但根据题目要求，所有位于任意两个开窗房间路径上的房间都应被统计，包括路径上关闭窗户的房间。例如：

• 连通块为A(开)-B(关)-C(开)，穿堂风经过A、B、C三个房间，正确的rooms应加3，但代码仅加2。

2. 并查集无法满足Rubik答案的计算需求 #

并查集只能维护连通块的整体属性（如总房间数、开窗房间数），无法追踪连通块内部的树形结构，因此无法判断哪些房间位于开窗房间的路径上。要正确计算Rubik的答案，必须遍历每个连通块的树形结构，标记符合条件的房间。

修改方案 #

改用邻接表存储图，通过DFS/BFS遍历每个连通块，结合树形结构分析统计结果：

1. 构建邻接表表示房间间的连通关系；
2. 遍历每个未访问的房间，找出完整的连通块；
3. 对每个连通块，统计开窗房间数量：
   • 若开窗数<2，无贡献；
   • 若开窗数≥2，计算该连通块中位于任意两个开窗房间路径上的房间数：
     • 通过后序遍历标记有效节点：若节点自身开窗，或其子树中存在开窗节点，则该节点为有效节点（被穿堂风经过）；
4. 累加所有连通块的穿堂风房间对数量（组合数C(k,2)，k为连通块开窗数）和有效节点数量。

修改后的代码示例 #

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> adj;
vector<int> windows;
vector<bool> visited;
vector<bool> is_valid;

int dfs(int u, int parent) {
    visited[u] = true;
    int has_open = windows[u]; // 自身是否开窗，或子树是否有开窗节点
    for (int v : adj[u]) {
        if (v == parent) continue;
        has_open += dfs(v, u);
    }
    // 若自身开窗，或子树中有开窗节点，则该节点有效
    is_valid[u] = (has_open > 0) && (windows[u] || has_open > windows[u]);
    return has_open;
}

pair<int, int> solve(int n) {
    int pairs = 0, rooms = 0;
    visited.assign(n+1, false);
    is_valid.assign(n+1, false);
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            int open_count = dfs(i, -1);
            if (open_count >= 2) {
                // 计算穿堂风房间对
                pairs += open_count * (open_count - 1) / 2;
                // 统计有效节点数
                int cnt = 0;
                for (int j = 1; j <= n; j++) {
                    if (visited[j] && is_valid[j]) {
                        cnt++;
                    }
                }
                rooms += cnt;
                // 重置visited中当前连通块的标记，避免影响下一个连通块
                for (int j = 1; j <= n; j++) {
                    if (visited[j]) visited[j] = false;
                }
            }
        }
    }
    return {pairs, rooms};
}

int main() {
    int N, M;
    cin >> N >> M;
    adj.resize(N+1);
    windows.resize(N+1);
    for (int i = 1; i <= N; i++) {
        cin >> windows[i];
    }
    while (M--) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    pair<int, int> ans = solve(N);
    cout << ans.first << " " << ans.second << endl;
    return 0;
}

内容的提问来源于stack exchange，提问作者Tapananshu Gandhi