[백준] 텀 프로젝트 (c++) dfs

출처 : https://www.acmicpc.net/problem/9466

 

풀이 방법

 

사이클을 찾는 문제이다.

사이클을 찾기 위해서, group을 만들고 dfs로 탐색을 했다.

group을 저장하기 위해 visited 배열을 사용했고, 해당 그룹에서의 사이클 원소 개수를 저장하기 위해 cnt_arr를 사용했다.

만약 visited가 0이라면 자신이 그룹의 시작으로 설정하고 탐색을 한다. 그러다 다음 원소가 자신의 그룹가 같다면 사이클이 완성되었다는 뜻이고, 그룹 중에서 몇 번째로 방문한 원소인지를 통해 사이클의 원소 개수를 구할 수 있었다.

 

풀이

 

#include <iostream>
#include <memory.h>
#include <vector>

using namespace std;

int t, n;
int visited[100001];
int cnt_arr[100001];
int graph[100001];
vector<int> ans;

void input() {
    cin >> n;
    for (int i = 0;i < n;i++) {
        cin >> graph[i];
        graph[i]--; // 그래프 인덱스 조정
    }
}

int dfs(int idx, int group, int cnt) {
    
    visited[idx] = group;
    cnt_arr[idx] = cnt;

    int next = graph[idx];
    if (visited[next] == group) { // 종료 조건, 루프 형성        
        return cnt - cnt_arr[next] + 1;
    }

    if (visited[next] == 0) {
        return dfs(next, group, cnt + 1);
    }
    else return 0;
}
void sol() {    
    input();
    int cnt = n;
    for (int i = 0;i < n;i++) {
        if (visited[i] == 0) {
            cnt -= dfs(i, i + 1, 1);
        }
    }
    ans.push_back(cnt);
}

int main() {

    cin >> t;

    for (int i = 0;i < t;i++) {
        memset(visited, 0, sizeof(visited));
        memset(cnt_arr, 0, sizeof(cnt_arr));
        sol();
    }
    for (int i = 0;i < ans.size();i++) {
        cout << ans[i] << endl;
    }
    return 0;
}