나의 풀이 :

T = int(input())
for tc in range(1, T + 1):
N, M = map(int, input().split())
bad_set = set()
for _ in range(M):
a, b = map(int, input().split())
k = 2**(a-1) + 2**(b-1)
bad_set.add(k)
ans = 0
for i in range(2**N):
for bad in bad_set:
if i & bad == bad:
break
else:
ans += 1
print('#{} {}'.format(tc, ans))


한마디 :

당연히 Timeout일 것으로 생각하고 Brute-Force 답안을 제출했는데 의외로 통과되었다. 부분집합의 갯수는 2**N 만큼 존재하는데, 각각 피해야 하는 조합과 Bitwise AND 연산을 해서 필터링 한다.