250x250
반응형
Notice
Recent Posts
Recent Comments
Link
N
(SWEA c++)2814. 최장경로 본문
728x90
반응형
DFS를 이용한 그래프 방문.
#include <iostream>
using namespace std;
int ans;
int N, M;
bool graph[11][11];
bool visited[11];
void dfs(int start, int current)
{
if(ans < current)
ans = current;
for(int i = 1; i <= N; i++)
{
if(graph[start][i] && !visited[i])
{
visited[i] = true;
dfs(i, current + 1);
visited[i] = false;
}
}
}
int main(void)
{
int t;
cin >> t;
for(int i = 1; i <= t; i++)
{
int x, y;
cin >> N >> M;
ans = 1;
for(int j = 0; j <= N; j++)
{
visited[j] = false;
for(int k = 0; k <= N; k++)
graph[j][k] = false;
}
for(int j = 0; j < M; j++)
{
cin >> x >> y;
graph[x][y] = true;
graph[y][x] = true;
}
for(int j = 1; j <= N; j++)
{
visited[j] = true;
dfs(j, 1);
visited[j] = false;
}
cout << "#" << i << " " << ans << endl;
}
return 0;
}
728x90
반응형
'SW Expert Academy' 카테고리의 다른 글
(SWEA c++)2948. 문자열 교집합 (0) | 2020.10.21 |
---|---|
(SWEA c++)2817. 부분 수열의 합 (0) | 2020.10.21 |
(SWEA c++)2805. 농작물 수확하기 (0) | 2020.10.21 |
(SWEA c++)2806. N-Queen (0) | 2020.10.20 |
(SWEA c++)1873. 상호의 배틀필드 (0) | 2020.10.20 |