[algospot][완전탐색] 소풍 : https://algospot.com/judge/problem/read/PICNIC

PICNIC.cpp

#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include<iostream>

using namespace std;

int n;
int ans = 0;
vector<int> check;
vector<set<int>> friends;

/* 
 * 시간복잡도 : O(N!)
 */

void solve(int ind) {
	if (ind == n) {
		ans++;
		return;
	}
	if (check[ind]) { //이미 짝인 경우
		solve(ind + 1); // 다음 인덱스 탐색
		return;
	}
	for (int i = ind+1; i < n; i++) {
		// 짝이 가능한 경우
		if (!check[i] && friends[ind].find(i) != friends[ind].end()){
			check[i] = true;
			solve(ind+1); // 다음 탐색
			check[i] = false;
		}
	}
}

int main() {
	int C;
	cin >> C;

	while (C--) {
		
		int m;
		cin >> n >> m;

		check = vector<int>(n, false);
		ans = 0;
		friends = vector<set<int>>(n);
		int a, b;

		for (int i = 0; i < m; i++) {
			cin >> a >> b;
			friends[a].insert(b);
			friends[b].insert(a);
		}
		solve(0);
		cout << ans << endl;
	}
	return 0;
}