def EnumerateSubgraphs(G, k):
N = len(G)
visited = [False] * N
queue = []
ans = 0
sub = {}
sub_graph = {}
for i in range(N):
queue.append([i])
while queue:
front = queue[0]
queue = queue[1:]
if len(front)==k:
degree = [0] * N
for f in front:
for j in front:
if G[f][j]==1:
degree[f] += 1
degree[j] += 1
if len(set(front)) != len(front):
continue
if str(sorted(front)) in sub_graph:
continue
sub_graph[str(sorted(front))] = 1
if str(sorted(degree)) in sub:
sub[str(sorted(degree))] += 1
else:
sub[str(sorted(degree))] = 1
print(front)
continue
for i in range(N):
if G[front[-1]][i]==1 and i > front[0]:
queue.append(front+[i])
for s in sub:
ans += sub[s]
return ans
G_adj = [[0, 0, 1, 0, 0],[0, 0, 1, 0, 0],[1, 1, 0, 1, 1],[0, 0, 1, 0, 1],[0, 0, 1, 1, 0]]
print("Start!")
ans = EnumerateSubgraphs(G_adj, k=5)
print(ans)
