#include #include #include #include using namespace std; /* Hopefully correct implementation. Didn't check yet! O(N^2), because we visit each edge once */ int main() { int n; cin >> n; assert(n >= 1); // adjacency matrix vector> beats(n, vector(n, false)); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { char c; cin >> c; if (c == 'X') continue; if (c == '1') beats[i][j] = true; } } vector visited(n, false); vector solution; function dfs = [&](int i) { assert(!visited[i]); visited[i] = true; for (int j = 0; j < n; ++j) { if (!beats[i][j]) continue; if (visited[j]) continue; dfs(j); } // when returning to node, add it to solution solution.push_back(i); // 0-based }; dfs(0); for (int i = 0; i < n; ++i) { if (!visited[i]) { cout << "impossible" << endl; return 0; } } assert(solution.size() == n); cout << solution[0]; for (int i = 1; i < n; ++i) { cout << ' ' << solution[i]; } cout << endl; }