PICNIC

https://algospot.com/judge/problem/read/PICNIC#

 

오름차순으로 조합하게끔 강제하여 중복으로 경우의 수를 세는 일이 없도록 한다.

 

#include <cstdio>
#include <cstring>

int t,n,m,a,b;
bool friends[10][10],check[10];

int count()
{
    int first=-1;
    for(int i=0;i<n;i++)
    {
        if(!check[i])
        {
            first=i;
            break;
        }
    }
    if(first==-1) return 1;
    int ret=0;
    for(int second=first+1;second<n;second++)
    {
        if(!check[second] && friends[first][second])
        {
            check[first]=check[second]=true;
            ret+=count();
            check[first]=check[second]=false;
        }
    }
    return ret;
}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&m);
        while(m--)
        {
            scanf("%d %d",&a,&b);
            friends[a][b]=friends[b][a]=true;
        }
        printf("%d\n",count());
        memset(friends,0,sizeof(friends));
        memset(check,0,sizeof(check));
    }
    return 0;
}