DFS를 이용한, 방향 그래프에서의 경로 탐색 in C++

1. 특정 방향그래프를 알려주는 간선이 입력으로 주어질때, 1번 정점에서 제일 큰 번호의 정점으로 가는 가지수를 출력하는 코드

첫째 줄에는, 정점의 수 N과, 간선의 수 M이 주어진다.

#include <iostream>
#include <vector>

using namespace std;
int n, m, cnt = 0;
int ch[101];
vector<int> V[101];

void DFS(int vertex) {
	if(vertex == n) {		// 종료 조건 
		cout << "path is : ";
		for(int i=1; i<=n; i++) {
			if(ch[i] == 1) cout << i << " ";
		}
		cout << "\n";
		cnt++;
	}
	else {
		for(int i=0; i<V[vertex].size(); i++) {
			int next_vertex = V[vertex][i];
			
			if(ch[next_vertex] == 0) {
				ch[next_vertex] = 1;
				DFS(next_vertex);
				ch[next_vertex] = 0;	
			}
		}
	} 
}

int main() {
	freopen("input.txt", "rt", stdin);
	cin >> n >> m;
	
	for(int i=1; i<=m; i++) {
		int a, b;
		cin >> a >> b;
		V[a].push_back(b);
	}
	ch[1] =1;		// 1번 정점에서 출발
	DFS(1);
	cout << cnt; 
	return 0;
} 

• V[a].push_back : vector의 배열을 선언하여, 해당 vertext에서 갈 수 있는 vertext를 삽입하였다.
• ch[next_vertex] = 1 : 해당 vertex를 방문하다고 가정 하였을 때
• ch[next_vertex] = 0 : 해당 vertex를 방문하지 않는다고 가정하였을 때

ex)
5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5