#include #include #include #include #include /* Backtrack solution for tournament fixing Should give time limit exceeded. It works backwards: start with Henk (the king in the end), and extend the game, Henk won in the last round, so before it was either king, or defeated someone. Work your way backwards like this, and you'll find a schedule. exponential complexity, I guess. */ using namespace std; int main() { int n; cin >> n; // adjacency lists vector> graph(n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { char c; cin >> c; if (c == '1') graph[i].push_back(j); } } vector done(n, false); done[0] = true; // Henk will always have played in the end int count = 1; deque solution; function recurse = [&](int i) { // everyone played if (count == n) { // initial player solution.push_front(i); cout << solution[0]; for (int j = 1; j < n; ++j) { cout << ' ' << solution[j]; } cout << endl; exit(0); } // For each person, where i wins, we can extend the game for (auto j : graph[i]) { if (done[j]) continue; // j has played in the recursive calls done[j] = true; count++; // extend in two ways: // beat j, continuing with i as king solution.push_front(j); recurse(i); solution.pop_front(); // or, we can continue with j as king solution.push_front(i); recurse(j); solution.pop_front(); // undo changes done[j] = false; count--; } }; // start the backtrack with Henk recurse(0); cout << "impossible" << endl; }