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

题目大意

题目描述
曾经有一棵包含 $n$ 个节点的无向树。为了让它更有趣，每条无向边都被随意赋予了一个方向，使其变成了一棵有向树。
现在树的结构和边的方向都遗失了，但给出了一份记录了这棵树连通性的矩阵。该连通性矩阵表现为 $n$ 个长度为 $n$ 的 01 字符串。如果第 $i$ 行的第 $j$ 个字符是 1，则代表在原图中存在一条从节点 $i$ 到节点 $j$ 的有向路径；如果是 0 则代表无法到达。（特别地，任何节点都始终可以到达它自身）。
你需要根据给出的连通性矩阵，判断是否存在符合条件的有向树结构。如果存在，请构造并输出任意一种满足条件的边连接方式；如果不存在，则指出无解。

输入格式
第一行包含一个整数 $t$ ($1 \le t \le 10^4$)，表示测试用例的数量。
每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 500$)，表示树的节点数量。
接下来的 $n$ 行，每行包含一个长度为 $n$ 的仅由 0 和 1 组成的字符串。第 $i$ 个字符串的第 $j$ 个字符为 1 当且仅当节点 $i$ 可以到达节点 $j$。
保证所有测试用例中 $n^3$ 的总和不超过 $500^3$。

输出格式
对于每个测试用例，如果存在满足条件的有向树，输出 Yes（大小写均可），并在随后的 $n-1$ 行中输出你构造的有向边。每行输出两个整数 $x$ 和 $y$，表示存在一条从 $x$ 指向 $y$ 的有向边（即 $x \to y$）。如果有多种合法的树结构，输出其中任意一种即可。
如果不存在满足条件的解，输出 No。

样例输入

11
4
1000
1111
1010
0001
4
1111
0111
0010
0111
4
0011
0111
0011
0001
4
1000
0110
0010
1111
4
1000
0110
1010
1111
5
10000
01011
00111
00010
00001
5
10000
11000
10101
10111
00001
5
10000
01101
00100
01110
10001
4
1100
0100
0011
0001
4
1110
0100
0010
0101
3
100
111
101

样例输出

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$，该结构刚好满足所有可达性限制。
对于第二个测试用例，可以证明不存在任何一种满足给出连通性的树结构。

说白了，就是给你点与点之间的联通情况，你要重建出一颗有向的树，能够满足题目的要求。

思路讲解

如果只是做一个 D1 的话，还是非常 easy 的。

只要一个点比如说 6，不出现在其他 2 可达的点中（比如说图上的 4,3,5,1）的可达性表上，那么 2,6 直接相连。（⚠️注意，之所以这么连，是因为如果不连这条边，可达性就无法满足了，我们采用这一策略是为了连最少的边，达到题目要求）

vector<pair<ll,ll>> edges;
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});
        }
    }
}

当然，最后需要写一个校验程序，也非常 easy 啊，先写一个东西校验这个树结构是否正确，然后再直接跑一遍可达性判断，看看和题目给出的是否一致。

do {
    if (SZ(edges)!=N-1) {
        cout<<"No\n";
        return;
    }
    vector<vector<ll>> g(N+2);
    for (auto [u,v]:edges) {
        merge(u,v);
        g[u].push_back(v);
    }
    // 对化为无向图后，树的可达性作校验
    set<ll> st;
    for (int i=1;i<=N;++i) {
        ll fai=find(i);
        st.insert(fai);
    }
    if (SZ(st)!=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);

AC代码

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

源代码

/**
 * Problem: D1. Tree Orientation (Easy Version)
 * Contest: Codeforces Round 1086 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2208/problem/D1
 * Created: 2026-03-15 10:58:12
 * 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;

/*
 *
 */
ll fa[MAXN];
ll find(ll x) {
    if (x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}
void merge(ll x,ll y) {
    ll fax=find(x),fay=find(y);
    if (fax==fay) {
        return;
    }
    fa[fax]=fay;
}
void Solve() {
    ll N;
    cin >> N;
    for (int i=1;i<=N;++i) {
        fa[i]=i;
    }
    vector<vector<char>> Reach(N+2,vector<char>(N+2));
    for (int i=1;i<=N;++i) {
        for (int j=1;j<=N;++j) {
            cin>>Reach[i][j];
        }
    }
    vector<pair<ll,ll>> edges;
    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});
            }
        }
    }
    do {
        if (SZ(edges)!=N-1) {
            cout<<"No\n";
            return;
        }
        vector<vector<ll>> g(N+2);
        for (auto [u,v]:edges) {
            merge(u,v);
            g[u].push_back(v);
        }
        // 对化为无向图后，树的可达性作校验
        set<ll> st;
        for (int i=1;i<=N;++i) {
            ll fai=find(i);
            st.insert(fai);
        }
        if (SZ(st)!=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/366753217

*/

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