Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
The matrix is not telling you the edges directly; it is telling you the transitive closure. Ask which reachable pairs are so “tight” that no third vertex can fit between them.
If can reach in an oriented tree and the path has length at least , then some internal vertex satisfies .
So a real directed edge should be exactly a cover relation: and there is no with and .
Build every such cover edge. The undirected version must be a tree, so it must have exactly edges and be connected. Trees are picky little bastards.
After constructing the cover graph, recompute reachability from these directed edges and compare it to the given matrix. If it matches, print the edges; otherwise print No.
Treat the given matrix as a reachability relation. Write when .
In an oriented tree, if reaches , the directed path from to must be the unique simple path between them in the underlying tree. There is nowhere else to go; trees do not give you scenic routes.
Now look at a reachable pair .
If the path from to has length at least , pick an internal vertex . Then
So cannot be a direct edge of the original tree.
On the other hand, if is an actual edge, there is no distinct vertex with . Such a would force a path from to going through , contradicting that and are adjacent in a tree.
Therefore the original directed edges are exactly the cover relations:
That is the whole trick. The matrix gives the transitive closure; we strip away everything implied by transitivity.
For every ordered pair with and , test all possible middle vertices . If no such exists, add the candidate directed edge .
Then validate the candidate graph:
and the undirected version must be connected. If this fails, it cannot be a tree.
Finally, recompute reachability using only these candidate directed edges. Compare the resulting matrix with the input. This final check cleanly catches bad diagonals, broken transitivity, mutual reachability, and all other random matrix nonsense.
First, assume the input really comes from some oriented tree. By the observation above, every original directed edge is a cover relation, and every cover relation is an original directed edge. So our candidate edge set is exactly the original tree's edge set. It has edges, is connected as an undirected graph, and its reachability matrix is exactly the input. The algorithm prints Yes.
Now assume the algorithm prints Yes. The candidate graph has edges and is connected when directions are ignored, so its underlying graph is a tree. The algorithm also recomputes reachability from the printed directed edges and verifies that it equals the given matrix. Therefore the printed directed tree is a valid construction.
So the algorithm accepts exactly the valid matrices.
Checking all triples costs
The final reachability recomputation on a tree costs , and validation with DSU is near-linear. The total complexity per test case is
with memory
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct DSU {
vector<int> p, sz;
DSU(int n) : p(n), sz(n, 1) {
iota(p.begin(), p.end(), 0);
}
int find(int x) {
while (x != p[x]) {
p[x] = p[p[x]];
x = p[x];
}
return x;
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
}
};
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<string> s(n);
for (auto &row : s) cin >> row;
vector<pair<int, int>> edges;
for (int u = 0; u < n; ++u) {
for (int v = 0; v < n; ++v) {
if (u == v || s[u][v] == '0') continue;
bool cover = true;
for (int w = 0; w < n; ++w) {
if (w == u || w == v) continue;
if (s[u][w] == '1' && s[w][v] == '1') {
cover = false;
break;
}
}
if (cover) edges.push_back({u, v});
}
}
bool ok = true;
if ((int)edges.size() != n - 1) ok = false;
if (ok) {
DSU dsu(n);
for (auto [u, v] : edges) dsu.unite(u, v);
int root = dsu.find(0);
for (int i = 1; i < n; ++i) {
if (dsu.find(i) != root) ok = false;
}
}
if (ok) {
vector<vector<int>> g(n);
for (auto [u, v] : edges) g[u].push_back(v);
vector<string> reach(n, string(n, '0'));
for (int start = 0; start < n; ++start) {
vector<int> st;
st.push_back(start);
reach[start][start] = '1';
for (int ptr = 0; ptr < (int)st.size(); ++ptr) {
int u = st[ptr];
for (int v : g[u]) {
if (reach[start][v] == '0') {
reach[start][v] = '1';
st.push_back(v);
}
}
}
}
if (reach != s) ok = false;
}
if (!ok) {
cout << "No\n";
} else {
cout << "Yes\n";
for (auto [u, v] : edges) {
cout << u + 1 << ' ' << v + 1 << '\n';
}
}
}
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct DSU {
vector<int> p, sz;
DSU(int n) : p(n), sz(n, 1) {
iota(p.begin(), p.end(), 0);
}
int find(int x) {
while (x != p[x]) {
p[x] = p[p[x]];
x = p[x];
}
return x;
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
}
};
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<string> s(n);
for (auto &row : s) cin >> row;
vector<pair<int, int>> edges;
for (int u = 0; u < n; ++u) {
for (int v = 0; v < n; ++v) {
if (u == v || s[u][v] == '0') continue;
bool cover = true;
for (int w = 0; w < n; ++w) {
if (w == u || w == v) continue;
if (s[u][w] == '1' && s[w][v] == '1') {
cover = false;
break;
}
}
if (cover) edges.push_back({u, v});
}
}
bool ok = true;
if ((int)edges.size() != n - 1) ok = false;
if (ok) {
DSU dsu(n);
for (auto [u, v] : edges) dsu.unite(u, v);
int root = dsu.find(0);
for (int i = 1; i < n; ++i) {
if (dsu.find(i) != root) ok = false;
}
}
if (ok) {
vector<vector<int>> g(n);
for (auto [u, v] : edges) g[u].push_back(v);
vector<string> reach(n, string(n, '0'));
for (int start = 0; start < n; ++start) {
vector<int> st;
st.push_back(start);
reach[start][start] = '1';
for (int ptr = 0; ptr < (int)st.size(); ++ptr) {
int u = st[ptr];
for (int v : g[u]) {
if (reach[start][v] == '0') {
reach[start][v] = '1';
st.push_back(v);
}
}
}
}
if (reach != s) ok = false;
}
if (!ok) {
cout << "No\n";
} else {
cout << "Yes\n";
for (auto [u, v] : edges) {
cout << u + 1 << ' ' << v + 1 << '\n';
}
}
}
}