문제 2140
방향 그래프 경로 탐색
문제 설명과 제한, 예시, 제출 가이드를 확인하고 바로 제출할 수 있습니다.
문제 설명
방향그래프의 1번 정점에서 N번 정점까지 가는 모든 경로의 경우 수를 출력하는 프로그램을 작성하시오. 아래 그래프 1번 정점에서 5번 정점으로 가는 가지 수는 아래와 같이 총 6가지이다.
1 2 3 4 5
1 2 5
1 3 4 2 5
1 3 4 5
1 4 2 5
1 4 5
1 2 3 4 5
1 2 5
1 3 4 2 5
1 3 4 5
1 4 2 5
1 4 5
입력 설명
첫 줄에 정점의 수 N(1<=N<=20)와 간선의 수 M이 공백으로 구분되어 입력된다.
두번 째 줄에 M줄에 걸쳐 간선의 정보가 주어진다.
두번 째 줄에 M줄에 걸쳐 간선의 정보가 주어진다.
출력 설명
총 가지 수를 출력한다.
입력 예시
5 9 1 2 2 1 1 3 1 4 2 3 3 4 2 5 4 2 4 5
출력 예시
6
출처
정보과학