2668_숫자고르기

Link : https://www.acmicpc.net/problem/2668

 접근

 dfs cycle을 이루는 노드들이 몇개인지 확인 한다

 1 2 3 4 5 6 7

 3 1 1 5 5 4 6

 

 1 - 3 - 1

 3 - 1 - 3

 5 - 5

 

 pivot 과 숫자를 함께 넘겨 준다

 만약 pivot으로 부터 출발하여

 노드 값이 pivot과 동일한 숫자가 나온다면

 답에 추가 한다

 

 dfs(int pivot, int node){

    if(visited[node])

        if( pivot == node )

            ret.push_back(pivot)

    else

        visited[node] = true

        dfs(pivot, node)

 }

 

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <algorithm>
#define MAX 101

using namespace std;

int visited[MAX];
int nums[MAX];
bool cycle[MAX];
int cnt;

void dfs(int pivot, int node){
    if(visited[node]){
        if(pivot == node){
            cycle[pivot] = true;
            cnt++;
            return;
        }
    }else{
        visited[node]=1;
        dfs(pivot, nums[node]);
    }
}

int main(int argc, const char * argv[]) {
    int n;
    //input
    scanf("%d", &n);
    for(int i = 1; i<=n ; i++){
        scanf("%d", &nums[i]);
    }
    
    cnt = 0;
    
    for(int i = 1 ; i <= n ; i++){
        
        dfs(i, i);
        memset(visited, 0, sizeof(visited));
    }
    
    printf("%d\n", cnt);
    for(int i = 1; i<= n ; i++){
        if(cycle[i]){
            printf("%d\n", i);
        }
    }
    
    return 0;
}