Codeforces 树定向问题：基于 DFS 和并查集的贪心解法

题目描述

给定一个包含 n 个节点的无向树，将 n-1 条边任意指定方向后形成有向树。已知所有节点对 (i, j) 的可达性矩阵（s[i][j] = 1 表示 i 能到达 j），请判断是否存在原树结构及一种边的定向方式使得可达性与矩阵完全一致。若存在，输出任意一种合法的有向边方案。

输入格式

多组测试数据。每组数据：

• 第一行 n（2 ≤ n ≤ 8000）
• 接下来 n 行，每行一个长度为 n 的 01 串，表示第 i 个节点对其他节点的可达性

输出格式

• 若无解，输出 No
• 若有解，输出 Yes，再输出 n-1 条有向边 x→y

---

核心观察

合法的结构本质是：每条直接边 u→v 一定是'一步直达'的关键节点。具体来说，对每个 u，它的直接儿子 v 一定是 u 能到达的点里，能到达最多点的那个点。因为 v 能覆盖一大片节点，只要连 u→v，u 就能通过 v 间接到达所有 v 能到达的点，这些点就不需要再和 u 连直接边了。

因此，在 u 能到达的点里，选可达点数最大的 v，u→v 这条边必须存在。

---

解题思路

1. 计算能力值

对每个点 u，计算 cnt[u] = 它能到达的点的数量（即它那一行 1 的个数）。cnt 越大，说明这个点越'强'，覆盖范围越广。

2. 排序

按能力从强到弱排序所有点，得到顺序：强点在前，弱点在后。

3. 贪心构造边

对每个 u：

1. 标记 u 自己已经'覆盖'。
2. 按从强到弱遍历所有点 v。
3. 如果 v 没被覆盖，且 u 能到达 v：
   • 连边 u → v
   • 把 v 能到达的所有点全部标记为已覆盖（因为 u 可以通过 v 间接到达它们，不需要再连直接边）
4. 重复直到所有可达点都被覆盖。

4. 验证

最后需验证三件事：

1. 边数必须正好是 n-1（必须是树）；
2. 这棵有向图必须连通（使用并查集检查）；
3. 重新跑一遍可达性（DFS），必须完全匹配输入矩阵。

满足就输出 Yes + 边，否则 No。

---

C++ 代码实现

#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 5;
int n, cnt[N], id[N]; // cnt[u]: u 的可达节点数; id: 排序后的节点编号
bool e[N][N], vis[N]; // e[u][v]: u 能否到 v; vis: 标记是否被覆盖
bool reach[N]; // DFS 验证时的可达标记
vector<int> tree[N]; // 构造的树的邻接表
vector<pair<int, int>> ans; // 存储最终的边

// 并查集
struct DSU {
    int fa[N];
    void init(int n) {
        for (int i = 1; i <= n; i++) fa[i] = i;
    }
    int find(int x) {
        return fa[x] == x ? x : (fa[x] = find(fa[x]));
    }
    void merge(int x, int y) {
        fa[find(x)] = find(y);
    }
} dsu;

// DFS：标记从 u 出发的所有可达节点
void dfs(int u) {
    reach[u] = 1;
    for (int v : tree[u]) {
        if (!reach[v]) dfs(v);
    }
}

// 排序规则：按可达数从多到少
bool cmp(int u, int v) {
    return cnt[u] > cnt[v];
}

void solve() {
    cin >> n;
    ans.clear();
    memset(cnt, 0, sizeof cnt);
    for (int i = 1; i <= n; i++) tree[i].clear();

    // 读入可达矩阵并统计 cnt
    for (int u = 1; u <= n; u++) {
        id[u] = u;
        string s;
        cin >> s;
        for (int v = 1; v <= n; v++) {
            e[u][v] = (s[v - 1] == '1');
            cnt[u] += e[u][v];
        }
    }

    // 按可达数排序节点
    sort(id + 1, id + n + 1, cmp);

    // 贪心构造边
    for (int u = 1; u <= n; u++) {
        memset(vis, 0, sizeof vis);
        vis[u] = 1; // 自身标记为覆盖
        for (int i = 1; i <= n; i++) {
            int v = id[i];
            if (!vis[v] && e[u][v]) {
                ans.push_back({u, v});
                if (ans.size() >= n) { // 边数超了，无解
                    cout << "No\n";
                    return;
                }
                // 标记 v 的所有可达节点为覆盖
                for (int w = 1; w <= n; w++) {
                    if (e[v][w]) vis[w] = 1;
                }
            }
        }
    }

    // 检查边数是否为 n-1
    if (ans.size() != n - 1) {
        cout << "No\n";
        return;
    }

    // 验证连通性
    dsu.init(n);
    for (auto p : ans) {
        int u = p.first, v = p.second;
        dsu.merge(u, v);
        tree[u].push_back(v);
    }

    // 检查所有节点是否连通
    int root = dsu.find(1);
    bool ok = 1;
    for (int i = 2; i <= n; i++) {
        if (dsu.find(i) != root) {
            ok = 0;
            break;
        }
    }
    if (!ok) {
        cout << "No\n";
        return;
    }

    // 验证可达性是否匹配
    for (int u = 1; u <= n; u++) {
        memset(reach, 0, sizeof reach);
        dfs(u);
        for (int v = 1; v <= n; v++) {
            if (reach[v] != e[u][v]) {
                ok = 0;
                break;
            }
        }
        if (!ok) break;
    }
    if (!ok) {
        cout << "No\n";
        return;
    }

    // 输出答案
    cout << "Yes\n";
    for (auto p : ans) {
        cout << p.first << " " << p.second << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}