SW 2814 최장 경로 [D3]

//DFS,, 최대 Length 구하기

#include <stdio.h>

#define MAX_N 10

#define MAX_M 20

int T, N, M;

int answer;

/*

배열 보는 방법

EX) N = 5, M = 5;

1 2, 1 3, 3 4, 3 5, 4 5 일때,

행 - N, 열 - M

Vertex는 1부터 시작, 따라서 0행은 비운다.

연결된 Vertex는 1열부터 차례대로 저장한다.

따라서 1번 Vertex와 연결된 Vertex는 총 2개이고(0번열 갯수) 2, 3번과 연결되어 있다.

0 1 2 3 4 5

0 0 0 0 0 0 0

1 2 2 3 0 0 0

2 1 1 0 0 0 0

3 3 1 4 5 0 0

4 2 3 5 0 0 0

5 2 3 4 0 0 0

*/

int arr[MAX_N+1][MAX_M+1]; //Vertex 1부터 시작, 0행은 사용하지 않는다.

int visit[MAX_N+1];

void init(){

answer = 0;

for (int i = 0; i < MAX_N + 1; i++)

for (int j = 0; j < MAX_M + 1; j++)

arr[i][j] = 0;

for (int i = 0; i < MAX_N+1; i++)

visit[i] = 0;

}

void DFS(int vertex, int length){

/*

1. 해당 vertex를 visit를 체크한다.

2. 방문하지 않았던 인접한 vertex를 방문한다.

3. 더이상 방문할 곳이 없다면 2로 돌아간다.

*/

//가장 큰 길이를 저장

answer = answer < length ? length : answer;

visit[vertex] = 1;

for (int i = 1; i <= arr[vertex][0]; i++){

//방문 안한 Vertex는 방문한다.

if (visit[arr[vertex][i]] == 0){

DFS(arr[vertex][i], length+1);

visit[arr[vertex][i]] = 0;

} 

}

visit[vertex] = 0;

}

int main(void)

{

scanf(" %d", &T);

for (int tc = 1; tc <= T; tc++){

scanf(" %d %d", &N, &M);

init();

/*각 Vertex별 인접한 Vertex 번호 저장

arr[VERTEX_NUM][0] 에는 헤당 Vertex에 인접한 Vertex의 수 저장*/

for (int i = 0; i < M; i++){

int v1, v2;

scanf(" %d %d", &v1, &v2);

int opt1 = 0, opt2 = 0;

for (int j = 1; j <= M; j++){

if (arr[v1][j] == 0 && opt1 == 0) {

arr[v1][j] = v2;

arr[v1][0]++;

opt1 = 1;

}

if (arr[v2][j] == 0 && opt2 == 0) {

arr[v2][j] = v1;

arr[v2][0]++;

opt2 = 1;

}

}

}

/*for (int i = 0; i <= N; i++){

for (int j = 0; j <= M; j++){

printf("%d ", arr[i][j]);

}

printf("\n");

}*/

for (int VertexNum = 1; VertexNum <= N; VertexNum++){

DFS(VertexNum, 1);

}

printf("#%d %d\n", tc, answer);

}

return 0;

}