7-15.球队“食物链”

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 55;

int n, flag = 0;
int g[N][N];
int res[N];
bool st[N];

void dfs(int u, int len) {
    if (flag) return;
    res[len] = u;

    // 搜完了
    if (len == n) {
        // 判断最后一个是不是与1相连，相连就说明这个是答案，因为字典序最小，所以第一个即可
        if (g[u][1] == 1) flag = 1;
        return;
    }

    // 判断是否成环，不成环直接不走，此处剪枝
    int loop = 0;
    for (int i = 1; i <= n; i++) {
        if (!st[i] && g[i][1] == 1) {
            // 因为字典序最小，所以找到第一个即可
            loop = 1;
            break;
        }
    }
    // 找不到环，所以结束（答案数组里的最后一个数需要和第一个数相连）
    if (loop == 0) return;

    // dfs 往下搜
    for (int i = 1; i <= n; i++) {
        int j = g[u][i];

        if (!st[i] && u != i && j == 1) {
            st[u] = true;
            dfs(i, len + 1);
            st[u] = false;
        }
    }
}

int main() {
//     freopen("in.txt", "r", stdin);
    cin >> n;

    memset(g, 0, sizeof g);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            char t;
            cin >> t;
            if (t == 'W') {
                g[i][j] = 1;
            } else if (t == 'L') {
                g[j][i] = 1;
            }
        }

    dfs(1, 1);
    if (flag) {
        for (int i = 1; i <= n; i++) {
            if (i == n)
                cout << res[i];
            else
                cout << res[i] << " ";
        }
    } else {
        cout << "No Solution" << endl;
    }
}