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

Problem

그래프상에서 연결요수개수의 집합 개수를 묻는 문제

Solution

adj 를 통해 인접 리스트를 DFS 방문

코드설명

1)adj배열을 통해 인접행렬을 최소화
2)adj의 각 idx값을 방문하면서 visited여부 판단
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)