가능한 모든 조합을 만드는 완전탐색을 이용해서 코드를 작성하였습니다.
여기서 중요한것은 중복을 피하는것인데 (0,1)과 (1,0)같이 중복된 경우가 세지면 안되기 때문에 먼저 현재 짝이 지어지지 않은 학생중 번호가 가장 작은 학생을 찾고, 그 학생의 짝을 찾는 방식으로 코드를 구현하였습니다.
번호가 가장 작은 학생을 찾을때는 초기값을 -1로 주고 짝이 지어지지않은 학생을 찾지 못하면(모든 학생이 짝을 지은 경우) 1을 리턴해주게 하였습니다.
짝을 찾는 과정은 백트래킹을 이용하여 구현하였습니다.
import sys
input = sys.stdin.readline
n = int(input())
def countPair():
student = -1
count = 0
for i, isVisit in enumerate(visit):
if (not isVisit):
student = i
break
if (student == -1): return 1
for i in range(student, len(visit), 1):
if (not visit[i] and isFriend[i][student]):
visit[i] = visit[student] = True
count += countPair()
visit[i] = visit[student] = False
return count
for _ in range(n):
studentCount, friendsPairCount = map(int, input().split())
visit = [False] * studentCount
isFriend = [[False] * studentCount for _ in range(studentCount)]
friendList = list(map(int, input().split()))
for j in range(0, len(friendList), 2):
isFriend[friendList[j]][friendList[j+1]] = True
isFriend[friendList[j+1]][friendList[j]] = True
print(countPair())