Solution
看到 \(01\) 矩阵，一个经典的转化是转化成二分图：建立 \(n\) 个行点 \(R_0 \sim R_{n-1}\) 与 \(n\) 个列点 \(C_0 \sim C_{n-1}\)，\(A_{i,j}\) 表示一条连接 \(R_i,C_j\) 的边。在此基础上可以想到两种建图方法：
Method 1
建无向图，\(A_{i,j}\) 作为边权。
不难发现原限制是 \(0/1\) 边各自的边导出子图为连通图的充分不必要条件。\(2n-1\) 条边恰好是一个生成树，但是发现生成树不好构造，我们就卡住了。
Method 2
建有向图，\(A_{i,j}\) 表示方向，转化成二分竞赛图：
- 若 \(A_{i,j}=1\)：建边 \(R_i \to C_j\)
- 若 \(A_{i,j}=0\)：建边 \(C_j \to R_i\)
那么原条件等价于原图中没有四元环。进一步地，可以归纳证明这样的二分图一定无环。即：二分竞赛图中，无四元环等价于整张图无环。
现在问题转化成了如何用 \(2n-1\) 条边表示这样一个有向无环二分图。我们只需要知道任意两点间的拓扑序大小关系。
注意到，若当前图中存在 \(k\) 个入度为 \(0\) 的点，在不取完这 \(k\) 个点之前，是不可能产生新的入度为 \(0\) 的点的。这样一层层剥掉入度为 \(0\) 的点，就将图分成了若干层。显然，同层内一定无边。那么我们只需要知道每个点所在的层。
显然，除第一层外，每个点必须有来自前一层的入边。对于每个点我们随便记录一条这样的边，会得到一个外向有向树森林，其中根为第一层的点，点在树中的深度就是它所在的层号。然后就做完了。
Code
#include "grid_encoding.h"
#include <vector>
#include <cstring>
#define rep(i,a,b) for(int i(a);i<b;++i)
#define rept(i,a,b) for(int i(a);i<=b;++i)
#define eb emplace_back
using namespace std;
namespace{const int N=1005;int n,in[N],d[N];vector<int> g[N],q;
}
void init(){memset(in,0,sizeof(in));memset(d,0,sizeof(d));rep(i,0,n*2) g[i].clear();q.clear(),q.reserve(n<<1);
}
void send(vector<vector<int>> A){n=A.size(),init();rep(i,0,n) rep(j,0,n){if(A[i][j]) g[i].eb(j+n),++in[j+n];else g[j+n].eb(i),++in[i];}rep(i,0,n*2) if(!in[i]) q.eb(i);while(!q.empty()){int u=q.back();q.pop_back();for(int v:g[u]){if(!--in[v]){q.eb(v);v>=n?select(u,v-n):select(v,u-n);}}}
}
vector<vector<int>> reconstruct(vector<vector<int>> B){n=B.size(),init();rep(i,0,n) rep(j,0,n){if(B[i][j]==1) g[i].eb(j+n),++in[j+n];else if(B[i][j]==0) g[j+n].eb(i),++in[i];}rep(i,0,n*2) if(!in[i]) q.eb(i);while(!q.empty()){int u=q.back();q.pop_back();for(int v:g[u]){if(!--in[v]){d[v]=d[u]+1;q.eb(v);}}}rep(i,0,n) rep(j,0,n){if(B[i][j]==-1) B[i][j]=d[i]<d[j+n];}return B;
}