CF2208D1 Tree Orientation (Easy Version)
XXh0919
·
·
题解
D1 切了 D2 没能场切，哈哈。
题目大意
你原本有一棵包含 n 个节点的无向树。为了让这棵树更有趣，你决定给这 n−1 条边中的每一条都任意指定一个方向。
随着时间推移，你忘记了这棵树的原始结构。但你找到了一张纸，上面记载了：在给所有边指定方向后，对于所有满足 1\le u,v\le n 的有序对 (u,v)，u 是否能到达 v。
你需要根据这张纸上的信息，还原出树的结构以及每条边的方向。
请判断是否存在合法解，并构造出一组解；如果存在多组合法解，输出任意一组即可。
## 解法
先考虑无解的情况。
首先比较显然的就是：如果一个点无法到达自己本身，那么无解。
其次就是：如果存在 $(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})$。这里给出 `bitset` 优化过后的代码。
::::success[Code]
```cpp
#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 300000
char 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] ++;
}
}
}
}//其实路径压缩就可以了，这里只是为了卡过 D2（然而最后没卡过）
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;
}
```
::::