Codeforces Round 1086 (Div. 2)——CF-2208-D1. Tree Orientation (Easy Version) · znzryb
## 题目大意
**题目描述**
曾经有一棵包含 $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 直接相连。（⚠️注意，之所以这么连，**是因为如果不连这条边，可达性就无法满足了**，我们采用这一策略是为了连最少的边，达到题目要求）
这个做法的正确性是这样的，**如果不连我们的算法所选择的边，可达性就无法满足了**。**如果比我们的这个做法连的边更多，要么你一定会改变这个可达性规律，要么你会把一棵树，变成一个环**。多也不行，少也不行，那我们的做法就是正确的了。
```cpp
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 啊，先写一个东西校验这个树结构是否正确，然后再直接跑一遍可达性判断，看看和题目给出的是否一致。
```cpp
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](https://codeforces.com/contest/2208/submission/366753217)
::: 源代码
```cpp
/**
* 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……）