#include <iostream>usingnamespacestd;inttestCase;//테스트 케이스 수intsCount;// 학생의 수intfCount;// 친구쌍의 수boolareFriends[10][10];// taken[i] = i번째 학생이 짝을 이미 찾았으면 true, 아니면 falseintcountPairings(booltaken[10]){//남은 학생들 중 가장 번호가 빠른 학생을 찾는다.intfirstFree=-1;for(inti=0;i<sCount;++i){if(!taken[i]){firstFree=i;break;}}//기저 사례 : 모든 학생이 짝을 찾았으면 한 가지 방법을 찾았으니 종료한다.if(firstFree==-1)return1;intret=0;// 이 학생과 짝지을 학생을 결정한다.for(intpairWith=firstFree+1;pairWith<sCount;++pairWith){if(!taken[pairWith]&&areFriends[firstFree][pairWith]){taken[firstFree]=taken[pairWith]=true;ret+=countPairings(taken);taken[firstFree]=taken[pairWith]=false;}}returnret;}intmain(void){intx,y;booltaken[10];inti,tc;cin>>testCase;int*result=newint[testCase];tc=testCase;i=0;while(testCase>0){cin>>sCount;cin>>fCount;for(inti=0;i<fCount;++i){cin>>x>>y;areFriends[x][y]=true;areFriends[y][x]=true;}result[i]=countPairings(taken);testCase--;i++;for(inti=0;i<10;++i)for(intj=0;j<10;j++)areFriends[i][j]=false;for(inti=0;i<10;++i)taken[i]=false;}for(inti=0;i<tc;++i)cout<<result[i]<<endl;return0;}
ghkd0205
9년 전