D1链接
D2链接
题意：给出n表示n个节点，其中有n-1条边构成了一棵树对于每个u，v给出字符串表示u是否可达v，判断是否能构造出这样一棵树，如果可以，打出每条边
D1 n的数据范围<=500
我们思考树变为有向图进而产生的性质：
树上无环
- u如果能到v，则v一定不能到u，否则会出现环
- 如果u到v有一条直接连边，则不能存在节点k，使得u->k,k->v的边存在，如果存在，去掉方向后会形成环。因此我们可以先假设u到v是一条直接连边，如果存在这样的k，就删去u到v的连边。相应的，如果u->k,k->v都是可达的，那么u->v也可达，如果不可达则不存在这样的树
由于n的数据范围，我们只需枚举k,u,v，删除u->v的多余边就是最后整个图的正确边，之后用并查集或者dfs判断整个图是否连通即可，整个时间复杂度是n^3;
代码：
查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
const int N=505;
int e[N][N],e1[N][N],fa[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);
}
void solve(){int n;cin>>n;char c;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>c;e[i][j]=c-'0';e1[i][j]=e[i][j];}}for(int i=1;i<=n;i++){if(e[i][i]!=1){cout<<"NO\n";return;}e1[i][i]=0;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j)continue;for(int k=1;k<=n;k++){if(k==i || k==j)continue;if(e[i][k]==1 && e[k][j]==1){if(e[i][j]==0){cout<<"NO\n";return;}e1[i][j]=0;}}}}for(int i=1;i<=n;i++)fa[i]=i;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(e1[i][j] && find(i)==find(j)){cout<<"NO\n";return;}if(e1[i][j])fa[find(j)]=find(i);}}for(int i=2;i<=n;i++)if(find(i)!=find(i-1)){cout<<"NO\n";return;}cout<<"YES\n";for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(e1[i][j])cout<<i<<' '<<j<<'\n';}}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;cin>>_;while(_--)solve();
}附：本题枚举k采用了Floyd算法的思想，是传递闭包的逆向思维传递闭包模版题
D2 n的数据范围<=8000
显而易见，n^3的做法必定超时。我们进一步去考虑基于树的有向图的性质：
对于一条路径u->k->w->v,由于u可达v，也就意味着，u同时也可达所有v可达的点，k和w点同理。
因此，在所有u可达的点中，进一步可达的点的数量最多的点肯定是和u为邻点，即u->k这一条边必定存在
之后，所有k可达的点必定和u之间没有直接连边
如图，我们可以在u->k1,u->k2直接构建边，同时用vis数组对，k1的可达点w1和k2的可达点w3做标记，表示u到这俩点的直接连边可忽略
所以总的算法流程：
先记录每个点的可达点的个数，然后从大到小排序，之后遍历每个点作为u，再去遍历它的所有可达点，如果vis数组未标记，则建边，同时把次可达点进行标记
时间复杂度O(n*(n+w));（这里注意，当边的条数>=n时直接cout<<NO，不然就变成n^3的复杂度了，或者用bitset优化也可以）
最后能得到n-1条边的无向图（如果不是n-1条边，直接cout<<NO），之后再dfs每个点，检查传递闭包是否和给出的数组相同
时间复杂度O(n*n)
总时间复杂度n^2，可以通过此题
代码如下：
查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
const int N=8e3+5;
int n,e[N][N];
struct pi{int id,cnt;bool operator<(const pi& a)const{return cnt>a.cnt;}
};
vector<pi> a;
struct DSU{int fa[N];void init(int n){for(int i=1;i<=n;i++)fa[i]=i;}int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}void in(int a,int b){int x=find(a),y=find(b);if(x==y)return;fa[x]=y;}
}dsu;
bool reach[N],vis[N];
vector<int> tree[N];
void dfs(int u){reach[u]=1;for(auto v:tree[u])dfs(v);
}
void solve(){cin>>n;a.clear();for(int i=1;i<=n;i++){tree[i].clear();}for(int u=1;u<=n;u++){char c;a.push_back({u,0});for(int v=1;v<=n;v++){cin>>c;e[u][v]=c-'0';a[u-1].cnt+=e[u][v];}}sort(a.begin(),a.end());vector<pair<int,int>> edg;for(int u=1;u<=n;u++){for(int i=1;i<=n;i++)vis[i]=false;vis[u]=true;for(int i=0;i<n;i++){int v=a[i].id;if(!vis[v] && e[u][v]==1){edg.push_back({u,v});vis[v]=true;if(edg.size()>=n){cout<<"NO\n";return;}for(int w=1;w<=n;w++){if(e[v][w])vis[w]=true;}}}}if(edg.size()!=n-1){cout<<"NO\n";return;}dsu.init(n);for(auto[u,v]:edg){dsu.in(u,v);tree[u].push_back(v);}int root=dsu.find(1);for(int i=2;i<=n;i++){if(dsu.find(i)!=root){cout<<"NO\n";return;}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)reach[j]=0;dfs(i);for(int j=1;j<=n;j++){if(reach[j]!=e[i][j]){cout<<"NO\n";return;}}}cout<<"YES\n";for(auto[u,v]:edg)cout<<u<<' '<<v<<'\n';
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;cin>>_;while(_--)solve();
}