Informatica Online Judge

  그래프 [0655 / 028F]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 47   Total Tried : 71


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

그래프에 대한 정보가 주어지고, 시작노드와 도착노드의 값이 입력되었을 때, 시작노드에서 도착노드로 갈 수 있는 서로 다른 경로의 개수를 구하시오.
단, 경로의 개수를 구하는 것에 있어서,

1. 한 노드를 두번이상 방문하는 것은 안된다.
2. 도착할 수 없는 경우, 0을 출력한다.
3. 시작노드와 출발노드가 동일할 경우, 1을 출력한다.


예를 들어, 아래의 그래프 같은 경우를 보자.



출발노드가 1, 도착노드가 4인 경우, 3을 출력한다.
출발노드가 1, 도착노드가 1인 경우, 1을 출력한다.
출발노드가 1, 도착노드가 8인 경우, 0을 출력한다.

Input

첫번째 줄에 노드의 수(n)와 간선의 수(k)가 공백으로 구분되어 입력된다. (단 n<20, k<100)
둘째 줄부터 k+1번째 줄까지, 간선이 연결되어 있는 노드가 입력된다.
k+2번째 줄에 출발노드와 도착노드가 순차적으로 입력된다.

Output

출발노드에서 도착노드까지의 경로의 개수를 출력한다.

IO Example

입력
8 8
1 2
1 4
1 5
2 3
3 4
3 7
4 6
5 6
1 4

출력
3

입력2
8 8
1 2
1 4
1 5
2 3
3 4
3 7
4 6
5 6
1 1

출력
1

입력3
8 8
1 2
1 4
1 5
2 3
3 4
3 7
4 6
5 6
1 8

출력
0

출제 : 권대희(GSHS-29th, 2012알고리즘수행평가)

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]