[백준 2668][DFS][C++] 숫자고르기

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

2668번: 숫자고르기

크기가 N인 배열이 주어지고, 각 칸에는 1 이상 N 이하인 정수가 들어갔을 때, 만들 수 있는 모든 사이클의 노드 개수와 노드를 정렬하여 출력하는 문제이다.

 

문제를 처음 접하였을 때, 모든 사이클이 아닌 가장 큰 사이클을 찾는 것이라 착각했는데, 경험의 부족인듯 하다(...)

 

루프 또한 사이클이므로 입력단계에서 미리 처리해주고 루프가 아닌 사이클을 모두 찾는 순서로 구현하였다.

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
	ios_base :: sync_with_stdio(false); 
	cin.tie(NULL); 
	cout.tie(NULL);
	
	int n, maxi=0; 
	cin>>n;
	vector<int> v(n+1), ans;
	vector<bool> visited(n+1);
	for(int i=1; i<=n; i++){
		cin>>v[i];
		if(i==v[i]){
			maxi++;
			ans.push_back(i);
			visited[i]=true;
		}
	}

	for(int i=1; i<=n; i++){
		int counter = 0, idx=i;
		vector<int> tmp;
		vector<bool> vis(n+1);
		while(!visited[idx] && !vis[idx]){
			counter++;
			tmp.push_back(idx);
			vis[idx]=true;
			idx=v[idx];
			if(idx==i) break;
		}
		if(idx!=i) continue;
		
		maxi += counter;
		for(int j : tmp){
			visited[j]=true;
			ans.push_back(j);	
		}
		
	}
	sort(ans.begin(),ans.end());
	
	cout<<maxi<<'\n';
	for(int i=0; i<ans.size(); i++){
		cout<<ans[i]<<'\n';
	}
	
}