picnic, 하

algospot.com :: PICNIC

문제

• 학생 수 $n(2\leq n \leq 10,\ 2\mid n)$와 $m(0\leq m \leq \binom{n}{2})$쌍의 친구관계가 주어진다
• 친구관계인 사람들끼리만 두명씩 짝지을 수 있는 경우의 수는?

 

$O(\frac{\binom{n}{2}\binom{n-2}{2}\cdot \cdot \cdot\binom{2}{2}}{\frac{n}{2}!})$

$n=10$일 때, 완전탐색을 진행하여도 $9 \cdot 7 \cdot 5 \cdot 3 = 945$번만 확인하면 된다

#include <bits/stdc++.h>
#define endl "\n"
#define ooop(i, n) for(int i = 0; i < n; i++)
#define loop(i, n) for(int i = 1; i <= n; i++)
using namespace std;
 
int n, m;
 
int countPairings(vector<bool>& taken, const vector<vector<bool> >& isfriend)
{
    int firstFree = -1;
    ooop(i, n){
        if(!taken[i]) {
            firstFree = i;
            break;
        }
    }
 
    if(firstFree == -1) return 1;
 
    int ret = 0;
    for(int i = firstFree + 1; i < n; i++){
        if(!taken[i] && isfriend[firstFree][i]){
            taken[firstFree] = taken[i] = true;
            ret += countPairings(taken, isfriend);
            taken[firstFree] = taken[i] = false;
        }
    }
 
    return ret;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        cin >> n >> m;
        vector<vector<bool> > isfriend(n, vector<bool>(n));
 
        int a, b;
        while(m--){
            cin >> a; cin >> b;
            isfriend[a][b] = true;
            isfriend[b][a] = true;
        }
 
        vector<bool> taken(n);
 
        cout << countPairings(taken, isfriend) << endl;
 
    }
 
    return 0;
}cs