[SWEXPERT] 2814. 최장 경로 (C++, D3)

어느 점에서 시작하는게 가장 긴 거리인지 모르므로 모든 점을 다 돌려본다.

DFS로 최대 들어갈 수 있는 깊이까지 들어간다고 보면 된다.

BFS써도 될거 같긴 하다.

 

#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
using namespace std;

int n, m,t;
vector<int> v[11];
bool vis[11];
int ans;

void dfs(int cnt,int num) {
	if (cnt > ans)ans = cnt;
	for (int i = 0; i < v[num].size(); i++) {
		int next = v[num][i];
		if (!vis[next]) {
            vis[next]=true;
			dfs(cnt + 1, next);
            vis[next]=false;
		}
	}

}

int main(void) {

	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> t;
	for (int tc = 1; tc <= t; tc++)
	{
		ans =1;
		for (int i = 1; i < 11; i++) {
			v[i].clear();
		}
		cin >> n >> m;
		for (int i = 0; i < m; i++) {
			int x, y;
			cin >> x >> y;
			v[x].push_back(y);
			v[y].push_back(x);
		}
		for (int i = 1; i < 11; i++) {
			memset(vis, false, sizeof vis);
            vis[i]=true;
			dfs(1,i);
		}
		cout << "#" << tc << " " << ans << "\n";
	
	}


	return 0;
}