PICNIC

문제링크

PICNIC

문제 풀이

N의 크기가 $2 \leq N \leq10$ 이므로 완전탐색으로 가능한 조합을 모두 만들어 본다. 아직 선택되지 않은 가장 빠른 번호의 학생부터 짝을 짓는다. 모두 다 짝이 지어졌으면 종료한다.

구현

#include <iostream>
#include <cstring>
using namespace std;

int TC, N, M;
bool arefriends[10][10], check[10];

int solve() {
    int start = -1;
    for (int i = 0; i < N; ++i) {
        if (!check[i]) {
            start = i;
            break;
        }
    }
    if (start == -1) return 1;

    int ret = 0;
    for (int i = start + 1; i < N; ++i) {
        if (!check[i] && arefriends[start][i]) {
            check[start] = check[i] = true;
            ret += solve();
            check[start] = check[i] = false;
        }
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> TC;
    while (TC--) {
        cin >> N >> M;
        memset(arefriends, 0, sizeof(arefriends));
        memset(check, 0, sizeof(check));
        for (int i = 0; i < M; ++i) {
            int x, y;
            cin >> x >> y;
            arefriends[x][y] = true;
            arefriends[y][x] = true;
        }
        cout << solve() << "\n";
    }
    return 0;
}