백준 2668번 - 숫자 고르기

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

두 집합이 일치하는지의 문제로 사이클이 존재하는 것들을 최대로 뽑으면 되는 문제이다.

N이 100밖에 안되기 때문에

모든 인자에 대하여 사이클 여부를 확인하는 식으로 진행해도 시간초과가 발생하지 않는다고 생각했다.

이전에 올린 9466번 텀 프로젝트와 유사하지만(사이클 문제)

N제한이 달라서 이번 문제가 더욱 수월하게 풀 수 있었다.

dfs로 방문을 할 수 있도록 했고 매개변수로는 처음 방문을 시작한 노드와 현재 방문중인 노드로 함수를 구현했다.

만약 방문을 한 적이 있고, 처음 시작한 노드와 같다면 사이클을 통해 다시 왔다는 것이기 때문에

해당 노드는 사이클이 존재한다고 판단하고 정답을 구할 수 있도록 했다.

#include <iostream>
#include <vector>
using namespace std;
 
int N;
vector<int> vec;
vector<int> visited;
vector<int> ans;
void dfs(int startNode,int currentNode){
    
    if(visited[currentNode]){
        if(currentNode==startNode)
            ans.push_back(startNode);
    }else{
        visited[currentNode]++;
        dfs(startNode,vec[currentNode]);
    }
    
}
int main(){
    
    cin>>N;
    
    vec=vector<int> (N+1,0);
    visited=vector<int> (N+1,0);
 
    for(int i=1;i<=N;i++){
        scanf("%d",&vec[i]);
    }
    
    for(int i=1;i<=N;i++){
        dfs(i,i);
        visited=vector<int> (N+1,0); //초기화
    }
    
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++){
        cout<<ans[i]<<endl;
    }
    
    return 0;
}