[C++] SWEA 최장 경로

출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GOPPaAeMDFAXB

 

 

 

풀이

#include <bits/stdc++.h>
using namespace std;

int result = 0;
map<int, vector<int>> nodes;

void dfs(int start, vector<bool> visited, int cnt) {
	visited[start] = true;
	for (int next : nodes[start]) {
		if (!visited[next]) {
			dfs(next, visited, cnt + 1);
		}
	}
	if (result < cnt){
		result = cnt;
		return;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int T;
	cin >> T;
	for (int t = 1; t <= T; t++)
	{
		int N, M;
		cin >> N >> M;
		vector<bool> visited(N+1, false);
		for (int i = 0; i < M; i++) {
			int a, b;
			cin >> a >> b;
			nodes[a].push_back(b);
			nodes[b].push_back(a);
		}
		for (int n = 1; n <= N; n++) {
			dfs(n, visited, 1);
			fill(visited.begin(), visited.end(), false);
		}
		cout << "#" << t << " " << result << endl;
		nodes.clear();
		result = 0;
	}
}

 

간단하고 재밌는 DFS 문제.

반례가 겹치지 않도록 visited를 인수로 받아서 관리하자.

1번 노드 뿐만 아니라, 다른 노드의 기준에서 최장 경로를 가질 수 있음에 유의하자.