[알고스팟] 소풍

algospot.com :: PICNIC

해설

고등학교때 배운 조합 문제이다. 경우의 수가 중복되지 않도록 순서를 강제 해야 된다

 

import sys
C = int(input())
for _ in range(C):
    N, M = map(int, sys.stdin.readline().rstrip().split())

    flist = list(map(int, sys.stdin.readline().rstrip().split()))
    friends = [[] for _ in range(10)]
    i = 0

    while i < len(flist):
        friends[flist[i]].append(flist[i+1])
        friends[flist[i+1]].append(flist[i])
        i += 2
    haveFriend = [False]*N

    def dfs(index):
        if all(haveFriend):
            return 1
        answer = 0
        for i in range(N):
            if not haveFriend[i] and i > index:
                for f in friends[i]:
                    if not haveFriend[f] and f > i:
                        haveFriend[i] = True
                        haveFriend[f] = True
                        answer += dfs(i)
                        haveFriend[i] = False
                        haveFriend[f] = False
        return answer

    print(dfs(-1))