由于这两个是同样的问题，所以这里是好题集第十七篇。
在这里还是%一下 zyn1919810 对✌，场切这两题 rk120。
题目大意
你原本有一棵包含 \(n\) 个节点的无向树。为了让这棵树更有趣，你决定给这 \(n−1\) 条边中的每一条都任意指定一个方向。
随着时间推移，你忘记了这棵树的原始结构。但你找到了一张纸，上面记载了：在给所有边指定方向后，对于所有满足 \(1\le u,v\le n\) 的有序对 \((u,v)\)，\(u\) 是否能到达 \(v\)。
你需要根据这张纸上的信息，还原出树的结构以及每条边的方向。
请判断是否存在合法解，并构造出一组解；如果存在多组合法解，输出任意一组即可。
Easy Version：\(2\le n\le 500\)。
Hard Version：\(2\le n\le 8000\)。
Solution for Easy Version
先考虑无解的情况。
首先比较显然的就是：如果一个点无法到达自己本身，那么无解。
其次就是：如果存在 \((u,v)\) 为 1 并且 \((v,u)\) 也为 1，那么无解。因为这样就相当于出现了一个环，而树是不能有环的。
再然后就是：如果存在 \((i,j),(j,k)\) 都为 1 并且 \((i,k)\) 为 0，那么无解。显然如果一个点能从另一个点转移到第三个点，那么这个点和第三个点是连通的。
那么剩下的就可能有解。考虑如何构造，我们先将每个点所能到达的点集存下来，然后依次遍历这些点集，构造每个点的出边即可。
需要注意的是第三种无解的情况的应用：如果 \((i,j),(j,k)\) 都为 1，那么就没必要连一条 \((i,k)\) 的边了。
最后还要判断图是否连通，不连通的话肯定就无解。
这部分可以 \(O(n^3)\) 完成，bitset 优化可以做到 \(O(\frac{n^3}{\omega})\)。
Code for Easy Version
#include <bits/stdc++.h>
#define loop(i,a,b) for(register int i=(a);~i;i=(b))
#define Mem(a,b) memset((a),(b),sizeof((a)))
#define eb emplace_back
#define pb push_back
using namespace std;
using i64 = long long;
using uint = unsigned int;
using ui64 = unsigned long long;
using i128 = __int128;
constexpr int N = 8000 + 15, mod = 998244353;namespace FAST_IO {
#define IOSIZE 300000char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)template <typename T> inline void read (T &x) { x = 0; T f = 1;char ch = getchar ();while (!isdigit (ch)) {if (ch == '-') f = -1; ch = getchar ();}while (isdigit (ch)) {x = (x << 1) + (x << 3) + (ch ^ '0'); ch = getchar ();} x *= f;}template <> inline void read (double &x) { x = 0; int f = 1;char ch = getchar ();while (!isdigit (ch)) { if (ch == '-') f = -1; ch = getchar ();} while (isdigit (ch)) x = x * 10 + (ch - '0'), ch = getchar ();if (ch == '.') {ch = getchar (); for (double t = 0.1; isdigit (ch); t *= 0.1) x += t * (ch - '0'), ch = getchar ();}x *= f;}inline void read(char &x) {char ch;while ((ch = getchar()) != EOF && isspace(ch));if (ch != EOF) x = ch;}inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }inline bool read(string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }template <typename T, typename ...Args> inline void read (T &x, Args &...args) {read(x); read(args...);}template <typename T> inline void write (T x) { if (x < 0) putchar ('-'), x = -x; if (x > 9) write (x / 10); putchar (x % 10 + 48);}inline void write(string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }inline void write(char *x) { while (*x) putchar(*x++); }inline void write(const char *x) { while (*x) putchar(*x++); }inline void write(char x) { putchar(x); }struct fio { ~fio () {if (p3 != obuf) { fwrite(obuf, 1, p3 - obuf, stdout);p3 = obuf;}}} io;template <typename T> fio& operator >> (fio &io, T &x) {return read (x), io;}template <typename T> fio& operator << (fio &io, const T &x) {return write (x), io;}
#define cin io
#define cout io
#define endl '\n'
}
using namespace FAST_IO;bool MS;int n;
string s[N];
int fa[N], rk[N];
int sz[N];int find (int x) {return x == fa[x] ? x : (fa[x] = find (fa[x]));
}void join (int x, int y) {int f1 = find (x), f2 = find (y);if (f1 != f2) {if (rk[f1] < rk[f2]) {fa[f1] = f2;} else {fa[f2] = f1;if (rk[f1] == rk[f2]) {rk[f1] ++;}}}
}inline void solve () {cin >> n;vector <bitset <N>>bit(n + 1);for (int i = 1; i <= n; ++ i) {cin >> s[i];for (int j = 1; j <= n; ++ j) {if (s[i][j - 1] == '1') bit[i].set (j);}}for (int i = 1; i <= n; ++ i)if (!bit[i][i]) { cout << "nO" << endl; return; }for (int i = 1; i <= n; ++ i)for (int j = i + 1; j <= n; ++ j)if (bit[i][j] && bit[j][i]) { cout << "nO" << endl; return; }for (int i = 1; i <= n; ++ i)for (int j = 1; j <= n; ++ j)if (bit[i][j] && (bit[j] & ~bit[i]).any ()) { cout << "nO" << endl; return; }for (int i = 1; i <= n; ++ i) sz[i] = bit[i].count();vector <int> ans (n);iota (ans.begin(), ans.end(), 1);sort (ans.begin(), ans.end(), [&](int x, int y) {return sz[x] > sz[y];});//一个点能够到达的节点越多说明它在原树中越浅vector <pair <int, int>> edges;for (int i = 1; i <= n; ++ i) {bitset<N> dir = bit[i];dir.reset (i);vector <int> nn;for (int j : ans) {if (j == i) continue;if (bit[i][j]) nn.eb(j);}for (int j : nn) {if (dir[j]) {edges.eb(i, j);dir &= ~bit[j];//去除满足 i->j->k 的所有 i->k 的边}}}if (edges.size() != n - 1) { cout << "nO" << endl; return; }for (int i = 1; i <= n; ++ i) fa[i] = i, rk[i] = 1;for (auto [u, v] : edges) join (u, v);int rt = find(1);for (int i = 2; i <= n; ++ i)if (find(i) != rt) { cout << "nO" << endl; return; }cout << "yEs" << endl;for (auto [u, v] : edges) cout << u << " " << v << endl;
}bool MT;int main () {int T_T;cin >> T_T;while (T_T --) solve ();return 0;
}
Solution for Hard Version
数据加强，需要我们用 \(O(n^2)\) 的复杂度才能通过。
依旧从原思路出发。其实判断可达性可以建反图用拓扑排序做，所以我们在判完上面无解的情况之后就把整张图的正图和反图都建下来，然后跑拓扑。拓扑的时候就遍历反图，如果这两个点在并查集中还没连上，然后就加上这条边。还是需要注意要将深度更大的节点排在前面，这样才方便合并。
跑完拓扑之后我们看一下所有点的度数是否全清零了，如果没有就说明出现了环，无解。
最后我们把新建出来的整棵树的矩阵表示出来，看和原来是否一样即可。
于是我们做到了 \(O(n^2)\)。
Code for Hard Version
#include <bits/stdc++.h>
#define Mem(a,b) memset((a),(b),sizeof((a)))
#define eb emplace_back
#define pb push_back
using namespace std;
using i64 = long long;
using uint = unsigned int;
using ui64 = unsigned long long;
using i128 = __int128;
constexpr int N = 8000 + 15, mod = 998244353;namespace FAST_IO {
#define IOSIZE 300000char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)template <typename T> inline void read (T &x) { x = 0; T f = 1;char ch = getchar ();while (!isdigit (ch)) {if (ch == '-') f = -1; ch = getchar ();}while (isdigit (ch)) {x = (x << 1) + (x << 3) + (ch ^ '0'); ch = getchar ();} x *= f;}template <> inline void read (double &x) { x = 0; int f = 1;char ch = getchar ();while (!isdigit (ch)) { if (ch == '-') f = -1; ch = getchar ();} while (isdigit (ch)) x = x * 10 + (ch - '0'), ch = getchar ();if (ch == '.') {ch = getchar (); for (double t = 0.1; isdigit (ch); t *= 0.1) x += t * (ch - '0'), ch = getchar ();}x *= f;}inline void read(char &x) {char ch;while ((ch = getchar()) != EOF && isspace(ch));if (ch != EOF) x = ch;}inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }inline bool read(string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }template <typename T, typename ...Args> inline void read (T &x, Args &...args) {read(x); read(args...);}template <typename T> inline void write (T x) { if (x < 0) putchar ('-'), x = -x; if (x > 9) write (x / 10); putchar (x % 10 + 48);}inline void write(string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }inline void write(char *x) { while (*x) putchar(*x++); }inline void write(const char *x) { while (*x) putchar(*x++); }inline void write(char x) { putchar(x); }struct fio { ~fio () {if (p3 != obuf) { fwrite(obuf, 1, p3 - obuf, stdout);p3 = obuf;}}} io;template <typename T> fio& operator >> (fio &io, T &x) {return read (x), io;}template <typename T> fio& operator << (fio &io, const T &x) {return write (x), io;}
#define cin io
#define cout io
#define endl '\n'
}
using namespace FAST_IO;bool MS;int n;
int deg[N];
int bit1[N][N], bit2[N][N];
int ansu[N], ansv[N];
vector <int> g[N], _g[N], e[N];
int dep[N];
int fa[N], rk[N];int find (int x) {while (x ^ fa[x]) x = fa[x] = fa[fa[x]];return x;
}void join (int x, int y) {int f1 = find (x), f2 = find (y);if (f1 != f2) {if (rk[f1] < rk[f2]) {fa[f1] = f2;} else {fa[f2] = f1;if (rk[f1] == rk[f2]) {rk[f1] ++;}}}
}int cnt;
inline void topo () {cnt = 0;int d = 0;queue <int> q;for (int i = 1; i <= n; ++ i) if (!deg[i]) q.emplace (i);while (!q.empty ()) {int u = q.front ();q.pop ();++ d;dep[u] = d;sort (_g[u].begin (), _g[u].end (), [&](int x, int y) {return dep[x] > dep[y];});//先处理子孙节点for (int v : _g[u]) {if (find (u) == find (v)) continue;join (u, v);++ cnt;ansu[cnt] = u, ansv[cnt] = v;e[u].eb (v);//加入新建出来的树}for (int v : g[u]) {deg[v] --;if (!deg[v]) q.emplace (v);}}
}inline void topo2 () {queue <int> q;for (int i = 1; i <= n; ++ i) if (!deg[i]) q.emplace (i);while (!q.empty ()) {int u = q.front ();q.pop ();bit2[u][u] = 1;for (int v : e[u]) {deg[v] --;if (!deg[v]) q.emplace (v);for (int i = 1; i <= n; ++ i) {if (bit2[u][i]) bit2[v][i] = 1;}}}
}//构建新树的矩阵inline void solve () {cin >> n;for (int i = 1; i <= n; ++ i) {deg[i] = 0, g[i].clear(), _g[i].clear (), dep[i] = 0, fa[i] = i, rk[i] = 1;e[i].clear ();for (int j = 1; j <= n; ++ j) {bit1[i][j] = bit2[i][j] = 0;}}for (int i = 1; i <= n; ++ i) {for (int j = 1; j <= n; ++ j) {char ch;cin >> ch;bit1[i][j] = (ch ^ '0');}}for (int i = 1; i <= n; ++ i){if (!bit1[i][i]) {cout << "NO" << endl;return; }bit1[i][i] = 0;}for (int i = 1; i <= n; ++ i) {for (int j = 1; j <= n; ++ j) {if (bit1[i][j] && bit1[j][i]) {cout << "No" << endl;return ;}}}for (int i = 1; i <= n; ++ i) {for (int j = 1; j <= n; ++ j) {if (bit1[i][j]) {g[i].eb (j);_g[j].eb (i);deg[j] ++;}}}topo ();if (cnt != n - 1) {cout << "nO" << endl;return ;}for (int i = 1; i <= n; ++ i) {if (deg[i]) {cout << "nO" << endl;return ;}deg[i] = 0;}for (int i = 1; i <= n; ++ i) {for (int j : e[i]) {deg[j] ++;}bit1[i][i] = 1;}topo2 ();for (int i = 1; i <= n; ++ i) {for (int j = 1; j <= n; ++ j) {if (bit1[i][j] ^ bit2[i][j]) {cout << "No" << endl;return ;}}}cout << "yEs" << endl;for (int i = 1; i <= cnt; ++ i) cout << ansv[i] << " " << ansu[i] << endl;
}bool MT;int main () {int T_T;cin >> T_T;while (T_T --) solve ();cerr << "Memory:" << (&MT - &MS) / 1048576.0 << "MB Time:" << clock() << "ms" << endl;return 0;
}