https://www.acmicpc.net/problem/11724

Problem

図面内の接続点数の集合数を尋ねる質問

Solution

隣接リストのDFSにadjでアクセス

コードの説明

1)adjアレイによる隣接行列の最小化
2)adjの各idx値にアクセスする際にアクセスするか否かを判断する
3)アクセスしていない場合は、再度dfsを呼び出します.

Python Code

import sys

N,M=map(int,sys.stdin.readline().split())

visited=[False]*(N+1)
result=[]
def dfs(depth,visited):
    if depth==M:
        for i in result:
            print(i,end=' ')
        print()
    else:
        for i in range(1,N+1):
            if not visited[i]:
                visited[i]=True
                result.append(i)
                dfs(depth+1,visited)
                result.pop()
                visited[i]=False
dfs(0,visited)