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.
Think of the given matrix as the transitive closure of the unknown directed tree. In a tree, a directed edge cannot be redundant: if the edge is , there is no other directed path from to .
If a solution exists, it is forced. The edges are exactly the cover pairs: iff reaches and there is no strict middle vertex with . The dumb version is .
Let be the set of vertices reachable from , and let . If and in any valid instance, then , so .
Fix a vertex . Among currently uncovered vertices reachable from , the one with maximum must be an immediate out-neighbor of . If it were deeper, its parent on the path from would also be uncovered and would have a larger reachable set.
Sort vertices by decreasing . For each , scan this order; when you find an uncovered reachable , add and mark all of covered. In a valid tree only edges are ever added, so marking whole rows is still . Then DFS-verify the constructed tree, because invalid matrices lie like hell.
Let
In an oriented tree, between two vertices there is only one undirected path. So if reaches , the directed path from to is that unique path.
Therefore a directed edge exists exactly when
That is just the cover relation of the reachability poset. So if a solution exists, it is unique. Nice, but checking every middle is cubic, which is dead on arrival for .
If and , then everything reachable from is also reachable from , and itself is not reachable from . Thus
Now fix one vertex . We want to find all direct edges going out of .
Suppose some reachable vertex is not a direct child of . Let be the first vertex after on the path from to . Then is a real edge and , so
So among all not-yet-covered vertices reachable from , the one with maximum must be a direct out-neighbor of . After we add , every vertex in is already reachable through that edge, so none of them can be another direct child of . Mark all of covered and continue.
Implementation-wise, sort vertices once by decreasing . For every :
In a valid tree, this reconstructs exactly the unique edge set.
The input can be complete nonsense, so do not try to prove it polite. Construct the candidate graph, then verify it brutally:
If all three pass, we have built a directed tree with the required reachability matrix. Otherwise, print No.
Sorting costs . For construction, every vertex scans candidates, and each accepted edge marks one whole row. Since we reject as soon as we would add edges, there are only row markings. Verification by DFS from every source is also .
So the total complexity per test case is
with memory for the matrix. The global constraint is exactly what makes this fit.
Reference used for cross-checking: official Codeforces editorial.
#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 = 0) {
init(n);
}
void init(int n) {
p.resize(n);
sz.assign(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> reach(n);
vector<int> cnt(n, 0), ord(n);
for (int i = 0; i < n; i++) {
cin >> reach[i];
ord[i] = i;
for (char c : reach[i]) cnt[i] += (c == '1');
}
sort(ord.begin(), ord.end(), [&](int a, int b) {
return cnt[a] > cnt[b];
});
vector<pair<int, int>> edges;
bool ok = true;
vector<char> covered(n);
for (int u = 0; u < n && ok; u++) {
fill(covered.begin(), covered.end(), 0);
covered[u] = 1;
for (int v : ord) {
if (!covered[v] && reach[u][v] == '1') {
edges.push_back({u, v});
if ((int)edges.size() >= n) {
ok = false;
break;
}
for (int w = 0; w < n; w++) {
if (reach[v][w] == '1') covered[w] = 1;
}
}
}
}
if (!ok || (int)edges.size() != n - 1) {
cout << "No\n";
continue;
}
DSU dsu(n);
vector<vector<int>> g(n);
for (auto [u, v] : edges) {
dsu.unite(u, v);
g[u].push_back(v);
}
int root = dsu.find(0);
for (int i = 1; i < n; i++) {
if (dsu.find(i) != root) ok = false;
}
vector<char> seen(n);
vector<int> st;
for (int src = 0; src < n && ok; src++) {
fill(seen.begin(), seen.end(), 0);
st.clear();
seen[src] = 1;
st.push_back(src);
while (!st.empty()) {
int u = st.back();
st.pop_back();
for (int v : g[u]) {
if (!seen[v]) {
seen[v] = 1;
st.push_back(v);
}
}
}
for (int v = 0; v < n; v++) {
if ((seen[v] ? '1' : '0') != reach[src][v]) {
ok = false;
break;
}
}
}
if (!ok) {
cout << "No\n";
continue;
}
cout << "Yes\n";
for (auto [u, v] : edges) {
cout << u + 1 << ' ' << v + 1 << '\n';
}
}
return 0;
}#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 = 0) {
init(n);
}
void init(int n) {
p.resize(n);
sz.assign(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> reach(n);
vector<int> cnt(n, 0), ord(n);
for (int i = 0; i < n; i++) {
cin >> reach[i];
ord[i] = i;
for (char c : reach[i]) cnt[i] += (c == '1');
}
sort(ord.begin(), ord.end(), [&](int a, int b) {
return cnt[a] > cnt[b];
});
vector<pair<int, int>> edges;
bool ok = true;
vector<char> covered(n);
for (int u = 0; u < n && ok; u++) {
fill(covered.begin(), covered.end(), 0);
covered[u] = 1;
for (int v : ord) {
if (!covered[v] && reach[u][v] == '1') {
edges.push_back({u, v});
if ((int)edges.size() >= n) {
ok = false;
break;
}
for (int w = 0; w < n; w++) {
if (reach[v][w] == '1') covered[w] = 1;
}
}
}
}
if (!ok || (int)edges.size() != n - 1) {
cout << "No\n";
continue;
}
DSU dsu(n);
vector<vector<int>> g(n);
for (auto [u, v] : edges) {
dsu.unite(u, v);
g[u].push_back(v);
}
int root = dsu.find(0);
for (int i = 1; i < n; i++) {
if (dsu.find(i) != root) ok = false;
}
vector<char> seen(n);
vector<int> st;
for (int src = 0; src < n && ok; src++) {
fill(seen.begin(), seen.end(), 0);
st.clear();
seen[src] = 1;
st.push_back(src);
while (!st.empty()) {
int u = st.back();
st.pop_back();
for (int v : g[u]) {
if (!seen[v]) {
seen[v] = 1;
st.push_back(v);
}
}
}
for (int v = 0; v < n; v++) {
if ((seen[v] ? '1' : '0') != reach[src][v]) {
ok = false;
break;
}
}
}
if (!ok) {
cout << "No\n";
continue;
}
cout << "Yes\n";
for (auto [u, v] : edges) {
cout << u + 1 << ' ' << v + 1 << '\n';
}
}
return 0;
}