第六题（NOIP2010）

#include<iostream>
using namespace std;
const int SIZE = 100;
int n, m, r[SIZE];
bool map[SIZE][SIZE], found;

bool successful() {
    int i;
    for (i = 1; i <= n; i++)
        if (!map[r[i]][r[i % n + 1]])
            return false;
    return true;
}

void swap(int* a, int* b) {
    int t;
    t = *a;
    *a = *b;
    *b = t;
}

void perm(int left, int right) {
    int i;
    if (found)
        return;
    if (left > right) {
        if (successful()) {
            for (i = 1; i <= n; i++) 
                cout << r[i] << " ";
            found = true;
        }
        return;
    }
    for (i = left; i <= right; i++) {
        swap(r + left, r + i);
        perm(left + 1, right);
        swap(r + left, r + i);
    }
}

int main() {
    int x, y, i;
    cin >> n >> m;
    memset(map, false, sizeof(map));
    for (i = 1; i <= m; i++) {
        cin >> x >> y;
        map[x][y] = true;
        map[y][x] = true;
    }
    for (i = 1; i <= n; i++)
        r[i] = i;
    found = false;
    perm(1, n);
    if (!found)
        cout << "No solution!" << endl;
    return 0;
}

1. 【判断题】在44行前加一个左斜杠，程序能正常运行，结果不变。
   {{ select(1) }}

• 正确
• 错误

2. 【判断题】去掉14行的*，运行结果不变。
   {{ select(2) }}

• 正确
• 错误

3. 【判断题】将48行删去不影响输出结果。
   {{ select(3) }}

• 正确
• 错误

4. 【判断题】将map类型改为int不会影响运行结果。
   {{ select(4) }}

• 正确
• 错误

5. 【选择题】该程序时间复杂度为（ ）。
   {{ select(5) }}

• O(nᵐ log n × mⁿ log m)
• O(n!)
• O(m! × n)
• O(n! × n)

6. 【选择题】输入：9 12 1 2 2 3 3 4 4 5 5 6 6 1 1 7 2 7 3 8 4 8 5 9 6 9
   输出（ ）。
   {{ select(6) }}

• 1 2 3 4 5 6 7 8 9
• 9 8 7 2 4 3 5 1 6
• 3 2 7 1 6 9 5 4 8
• 1 6 9 5 4 8 3 2 7