멱집합(부분집합) 응용, 조건에 따라 불필요한 부분집합 제거

#include <stdio.h>
 
#define N 21
#define M 401
 
typedef struct{
 int one;
 int two;
}Pair;
 
Pair P[M];
int Num;
int MNum;
int TC;
int Tccn = 1;
 
int ResultCnt = 0;
int Print[4000];
void input()
{
 int i, j, k;
 
 ResultCnt = 0;
 //집합의 개수
 scanf("%d %d", &Num, &MNum);
 //집합의 개수만큼 집합의 데이터를 입력받는다.
 for (i = 1; i <= MNum; i++)
 {
  scanf("%d %d", &P[i].one, &P[i].two);
 }
}
int PairCheck()
{
 int i, j;
 int cnt = 0;
 
 for (j = 1; j <= MNum; j++)
 {
  // 현재 부분집합 Flag를 가진 Print 배열에서, one, two의 인자에 대한 값이 둘 다 1일 경우 바로 Return
  if (Print[P[j].one] == 1 && Print[P[j].two] == 1)
  {
    return 1;
  }
 }
 
 return 0;
}
void process(int index)
{
 int i, j;
 
 if (index > Num)
 {
  //현재 안어울리는 조합이 있을 경우 return
  if (PairCheck())
   return;
  else
  {
   ResultCnt++;
   return;
  }
 }
 
 //부분집합 구하기 위한 Bactracing
 // 1일 때와 0일 때를 구분
 Print[index] = 1;
 process(index + 1);
 Print[index] = 0;
 process(index + 1);
}
void output()
{
 printf("%d\n",  ResultCnt);
 ResultCnt = 0;
}
int main(void)
{
 //freopen("input.txt", "r", stdin);
 //freopen("output.txt", "w", stdout);
 
 int TC;
 scanf("%d", &TC);
 while (TC--)
 {
  input();
  process(1);
  output();
 }
 return 0;
}