[SWEA] 최장 경로

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

풀이

백트래킹을 통해서 해결하였다. 모든 점을 다 탐색하어 최장 길이를 구할 수 있다.

코드

#include <iostream>
#include <cstring>
using namespace std;

int n, m, ans;
bool adj[11][11];
bool visited[11];

void dfs(int idx, int cnt) {
    ans = ans > cnt ? ans : cnt;
    visited[idx] = true;

    for (int i = 1; i <= n; i++) {
        if (!visited[i] && adj[idx][i])
            dfs(i, cnt + 1);
    }
    visited[idx] = false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    for (int c = 1; c <= t; c++) {
        ans = 1;
        cin >> n >> m;
        memset(adj, false, sizeof(adj));
        memset(visited, false, sizeof(visited));
        for (int i = 0; i < m; i++) {
            int tmp1, tmp2;
            cin >> tmp1 >> tmp2;
            adj[tmp1][tmp2] = true;
            adj[tmp2][tmp1] = true;
        }
        for (int i = 1; i <= n; i++) {
            dfs(i, 1);
        }
        cout << "#" << c << ' ' << ans << '\n';
    }
}