Codeforces Round 1086 (Div. 2)——CF-2208-D2. Tree Orientation (Hard Version)

题目大意

题目描述
有一棵包含 $n$ 个节点的无向树，为了让它更有趣，你对它的 $n-1$ 条边任意指定了方向，将其变成了一棵有向树。
现在你忘记了这棵树的结构和边的方向，但你找到了一份记录，上面写着给边指定方向后，所有节点对之间的可达性。具体来说，给定 $n$ 个长度为 $n$ 的 01 字符串。如果第 $i$ 个字符串的第 $j$ 个字符为 1，则表示在有向树中，节点 $i$ 可以到达节点 $j$ （必然存在一条从 $i$ 到 $j$ 的有向路径）；如果为 0 则表示无法到达。特别地，一个节点总是可以到达它自己。

你的任务是根据这个可达性信息，判断是否存在合法的树结构与边的方向。如果存在，请构造并输出任意一个满足条件的解；如果不存在，请输出 No。本题为 Hard 版本，与 Easy 版本的唯一区别是 $n$ 的数据范围更大。

输入格式
第一行包含一个整数 $t$ （ $1 \le t \le 10^4$ ），表示测试用例的数量。
每个测试用例的第一行包含一个整数 $n$ （ $2 \le n \le 8000$ ），表示节点的数量。
接下来 $n$ 行，每行包含一个长度为 $n$ 的 01 字符串，表示可达性矩阵。
保证所有测试用例中 $n^2$ 的总和不超过 $8000^2$ 。

输出格式
对于每个测试用例，如果存在解，输出 Yes，并在接下来的 $n-1$ 行中输出构造的有向边。每行包含两个整数 $x$ 和 $y$ ，表示存在一条从 $x$ 指向 $y$ 的有向边。如果有多个解，输出任意一个即可。
如果不存在解，输出 No。
（输出 Yes 和 No 时不区分大小写，例如 yEs、YES 都会被接受）。

样例输入

样例输出

Yes
2 3
2 4
3 1
No
No
Yes
2 3
4 1
4 2
No
No
Yes
2 1
3 1
3 5
4 3
No
No
Yes
1 2
1 3
4 2
Yes
2 3
3 1

样例解释
对于第一个测试用例，给定的矩阵表示：节点 $1$ 和 $4$ 只能到达它们自己，节点 $2$ 可以到达所有节点，节点 $3$ 只能到达节点 $1$ 和 $3$ 。输出构造的边为 $2 \to 3$ 、 $2 \to 4$ 、 $3 \to 1$ ，这三条边构成了一棵合法的有向树，并且恰好满足上述可达性限制。
对于第二个测试用例，可以证明不存在任何合法的一棵树能够满足给定的可达性要求，因此输出 No。

思路讲解

Codeforces Round 1086 (Div. 2)——CF-2208-D1. Tree Orientation (Easy Version)

这道题目的简单版本确实是比较 easy 的。

Codeforces Round 1085 (Div. 1 + Div. 2)——CF-2207-E1. N-MEX (Constructive Version)

我觉得和这道题目有一点像，都是要使用这个贪心方法，来解决一些问题。

具体而言，我们要解决的，就是这个两个循环。我们发现，现在的问题在于，全部的 a，都要把全部的 b 给遍历一遍。这个太耗时耗力了。说白了，这个其实是一个连通性问题，即根节点 i，能不能通过一个中间点 b，访问到这个 a？当然，我们可以把

for (int i=1;i<=N;++i) {
    vector<ll> nodes;
    for (int j=1;j<=N;++j) {
        if (j==i) continue;
        if (Reach[i][j]=='1') {
            nodes.push_back(j);
        }
    }
    for (auto a:nodes) {
        bool ok=true;
        for (auto b:nodes) {
            if (b==a) continue;
            if (Reach[b][a]=='1') {
                ok=false;
                break;
            }
        }
        if (ok) {
            edges.push_back({i,a});
        }
    }
}

我们可以使用离线思想和排序思想，找到一种顺序，使得先处理顺序靠前的，后处理顺序靠后的，不会造成问题。

我们可以按照 cnt_reach（即所有可到达点的数量） 降序排序。

为什么降序排列有效？ cnt_reach 最大的节点，其子树规模最大。在合法树中， $i$ 的各个孩子的子树是互不相交的。最大子树的根必定是直系孩子（不可能被更小的子树"遮挡"），所以先处理最大的是安全的。

for (int i=1;i<=N;++i) {
    vector<ll> nodes;
    dsu.init(N);
    for (int j=1;j<=N;++j) {
        if (j==i) continue;
        if (Reach[i][j]=='1') {
            nodes.push_back(j);
        }
    }
    ll guard=0;
    sort(all(nodes),[&](const ll &a,const ll &b) {
        return cnt_reach[a]>cnt_reach[b];
    });
    for (auto a:nodes) {
        // 想恶意卡我？没门
        if (guard>N) {
            cout<<"No\n";
            return;
        }
        if (!dsu.same(i,a)) {
            guard+=cnt_reach[a];
            edges.emplace_back(i,a);
            dsu.merge(i,a);
            for (auto b:node_reach[a]) {
                dsu.merge(i,b);
            }
        }
    }
}

AI对我们做法的总结

虽然我无法访问到当前的文件系统（worktree 似乎已被清理），但根据我们之前的深入讨论和我读过的代码，我可以完整总结我们的做法。

总结：D2. Tree Orientation (Hard Version) 的做法

核心思路

给定一个 $n \times n$ 的可达性矩阵 Reach，要求还原一棵 $n$ 个节点的有向树（ $n-1$ 条边）使得可达性与输入一致。
关键观察：如果 Reach[i][j] = '1'，说明 $i$ 能到达 $j$ 。在有向树中， $i$ 的直系孩子 $c$ 满足： $i$ 能到 $c$ ，且不存在中间节点 $b$ 使得 $i \to b \to \cdots \to c$ 。
D1 的 $O(N^3)$ 做法是暴力三重循环：对每个 $i$ ，枚举候选孩子 $a$ ，再枚举所有其他节点 $b$ 检查 Reach[b][a] 来判断 $a$ 是否被某个 $b$ “遮挡”。

D2 的 $O(N^2)$ 优化

第一步：预处理。 对每个节点 $i$ ，计算 cnt_reach[i]（ $i$ 能到达的节点数，不含自身）和 node_reach[i]（ $i$ 能到达的节点列表）。
第二步：贪心找直系孩子。 对每个节点 $i$ ：

将 $i$ 能到达的所有节点按 cnt_reach 降序排列。
初始化一个局部 DSU。
按排好的顺序遍历候选节点 $a$ ：

若 dsu.same(i, a) 为真，说明 $a$ 已经被某个先前确认的孩子的子树覆盖，跳过。
否则， $a$ 是 $i$ 的一个直系孩子。连边 $(i, a)$ ，然后把 node_reach[a] 中的所有节点 merge 进 $i$ 的 DSU 分量，同时把 $a$ 本身也 merge 进去。
为什么降序排列有效？ cnt_reach 最大的节点，其子树规模最大。在合法树中， $i$ 的各个孩子的子树是互不相交的。最大子树的根必定是直系孩子（不可能被更小的子树"遮挡"），所以先处理最大的是安全的。
复杂度分析： 对合法输入，每个节点 $i$ 的所有直系孩子的子树大小之和恰好等于 $|R(i)| - 1$ ，即 merge 操作的总量不超过 $O(N)$ 。遍历候选也是 $O(|R(i)|)$ 。因此所有节点加起来是 $O(N^2)$ 。
第三步：防御性 guard。 累加实际被选为孩子的节点的 cnt_reach 值（仅对真正的孩子累加，不是对所有候选节点）。如果这个累加和超过 $N$ ，说明输入矩阵不合法，直接输出 “No”。这个 guard 同时也防止恶意输入把复杂度卡到 $O(N^3)$ 。
第四步：验证。 构造完所有边后：

检查边数是否恰好 $N-1$ 。
用 DSU 检查是否连通（构成一棵树）。
从每个节点 BFS，重建可达性矩阵 $R$ ，与输入 Reach 逐位比较。不一致则输出 “No”。

关键修复点（相比 D1 代码的改动）

用 DSU 替代 $O(N^3)$ 枚举：这是核心优化。不再对每个候选 $a$ 暴力枚举所有 $b$ 判断 Reach[b][a]，而是利用排序 + DSU 在 $O(N^2)$ 内完成。
guard 位置修正：guard += cnt_reach[a] 必须放在 if (!dsu.same(i,a)) 内部，只对实际选中的孩子计数。放在外面会对链状合法输入误判为 “No”。
自身 merge：确认孩子 $a$ 后，除了 merge node_reach[a] 的所有节点，还需要 dsu.merge(i, a) 把 $a$ 本身也并入。

一句话总结

按子树大小降序贪心 + DSU 快速跳过已覆盖节点 + BFS 回代验证，将 D1 的 $O(N^3)$ 传递归约优化为 $O(N^2)$ 。

AC代码

AC
https://codeforces.com/contest/2208/submission/366894699

源代码

/**
 * Problem: D2. Tree Orientation (Hard Version)
 * Contest: Codeforces Round 1086 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2208/problem/D2
 * Created: 2026-03-16 13:00:28
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */


/**   并查集（DSU）
 *    2023-08-04: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=63239142 (base on jiangly)
 *    2025-11-08: https://frp-shy.com:32768/domjudge/team H题 增加dsu on next，标记区间l，r的功能
 *    为了适配这个dsu on next，对merge 函数合并方向进行了修改。
 *    2025-12-05：https://codeforces.com/contest/2171/submission/351963922
 *    增加了 countFa 功能
 *    2025-12-23：移除了宏定义，增加功能说明模块。
 *    功能说明：dsu on next，find(x)，就是在 x 之后第一个没有被标记的数字
 *    该 dsu 传入构造函数的这个大小，需要是 n 就是 n，如果你不希望 countFa 出错的话。
**/
struct DSU {
    vector<int> fa/*, siz*/;
    ll n;

    DSU() {}
    DSU(ll n):n(n){
        init(n);
    }

    void init(ll n) {
        n+=5;
        fa.resize(n);
        for(int i=0;i<SZ(fa);++i) {
            fa[i]=i;
        }
        // siz.assign(n, 1);
    }

    ll find(ll x) {
        while (x != fa[x]) {
            x = fa[x] = fa[fa[x]];
        }
        return x;
    }

    bool same(ll x,ll y) {
        return find(x) == find(y);
    }

    bool merge(ll x, ll y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        // siz[y] += siz[x];
        fa[x] = y;
        return true;
    }

    // ll size(ll x) {
        // return siz[find(x)];
    // }

    // dsu on next 技巧，直接标记 [l,r] 这段区间
    // 标记就是指让[l,r]这段区间里的所有数字这个都不指向自己
    // 可以理解为指向 r+1
    void taglr(ll l,ll r) {
        l=max(0ll,l);
        r=min(SZ(fa)-2,r);
        l=find(l);
        while(l<=r) {
            merge(l,l+1);
            l+=1;
            l=find(l);
        }
    }
    // 如果想让 countFa 结果准确，传入的 n 必须不多不少
    ll countFa() {
        ll res=0;
        for(int i=1;i<=n;++i) {
            if (fa[i]==i) {
                ++res;
            }
        }
        return res;
    }
};

void Solve() {
    ll N;
    cin >> N;
    vector<vector<char>> Reach(N+2,vector<char>(N+2));
    vector<vector<int>> node_reach(N+2);
    vector<ll> cnt_reach(N+2);
    for (int i=1;i<=N;++i) {
        for (int j=1;j<=N;++j) {
            cin>>Reach[i][j];
            if (j==i) continue;
            if (Reach[i][j]=='1') {
                cnt_reach[i]++;
                node_reach[i].push_back(j);
            }
        }
    }
    vector<pair<ll,ll>> edges;
    DSU dsu(N);
    for (int i=1;i<=N;++i) {
        vector<ll> nodes;
        dsu.init(N);
        for (int j=1;j<=N;++j) {
            if (j==i) continue;
            if (Reach[i][j]=='1') {
                nodes.push_back(j);
            }
        }
        ll guard=0;
        sort(all(nodes),[&](const ll &a,const ll &b) {
            return cnt_reach[a]>cnt_reach[b];
        });
        for (auto a:nodes) {
            // 像恶意卡我？没门
            if (guard>N) {
                cout<<"No\n";
                return;
            }
            if (!dsu.same(i,a)) {
                guard+=cnt_reach[a];
                edges.emplace_back(i,a);
                dsu.merge(i,a);
                for (auto b:node_reach[a]) {
                    dsu.merge(i,b);
                }
            }
        }
        // for (auto a:nodes) {
        //     bool ok=true;
        //     for (auto b:nodes) {
        //         if (b==a) continue;
        //         if (Reach[b][a]=='1') {
        //             ok=false;
        //             break;
        //         }
        //     }
        //     if (ok) {
        //         edges.push_back({i,a});
        //     }
        // }
    }
    do {
        DSU dsu_check(N);
        if (SZ(edges)!=N-1) {
            cout<<"No\n";
            return;
        }
        vector<vector<ll>> g(N+2);
        for (auto [u,v]:edges) {
            dsu_check.merge(u,v);
            g[u].push_back(v);
        }
        // 对化为无向图后，树的可达性作校验
        if (dsu_check.countFa()!=1) {
            cout<<"No\n";
            return;
        }
        // 直接模拟，校验我们所构造
        vector<vector<char>> R(N+2,vector<char>(N+2,'0'));
        for (int i=1;i<=N;++i) {
            queue<ll> q;
            q.push(i);
            R[i][i]='1';
            while (!q.empty()) {
                ll a=q.front();
                q.pop();
                for (auto v:g[a]) {
                    if (R[i][v]=='1') {
                        continue;
                    }
                    R[i][v]='1';
                    q.push(v);
                }
            }
        }
        for (int i=1;i<=N;++i) {
            for (int j=1;j<=N;++j) {
                if (Reach[i][j]!=R[i][j]) {
                    cout<<"No\n";
                    return;
                }
            }
        }
    }while (false);

    cout<<"Yes\n";
    for (auto [u,v]:edges) {
        cout<<u<<" "<<v<<"\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}


/*
AC
https://codeforces.com/contest/2208/submission/366894699

1
4
1000
1111
1010
0001

_______________[ Stress test, testcase 6170 INPUT ]_______________
1
4
1101
0100
1111
0001

_______________[ Stress test, testcase 6170 OUTPUT]_______________
No

*/

心路历程（WA，TLE，MLE……）

_______________[ Stress test, testcase 6170 INPUT ]_______________
1
4
1101
0100
1111
0001

_______________[ Stress test, testcase 6170 OUTPUT]_______________
No