처음에는 combination으로 모든 조합을 다 구해봤다. 당연히 시간초과가 났다. N이 100 이하니까 당연한 결과였다.
그래서 다시 생각한 방법이 일단 map을 만들었다. key 값을 1~N까지로 하고 둘째 줄에 들어있는 값들을 value로 해서 넣었다.
그 다음에 i = 1부터 시작해서 i = N까지 반복을 하였다. 예를 들어 i = 1이라면 map[1]에 있는 value를 key에 대입하여 이제 map[1]이 key가 된다. 그 다음에 또 그 key를 가지고 map[key]로 간다. 그 다음에도 또 반복을 하는 것이다. 그런데 이미 방문했던 곳이라면 사이클이 생겼거나 숫자가 중복된다는 것이다. 숫자가 중복됐다는 것은 잘못된 것이다. 왜냐하면 첫번째 줄은 1부터 N이므로 숫자가 중복될 수가 없다. 사이클이 생긴 곳은 visited에 방문했다고 표시한다. 이런 식으로 사이클이 생긴 것들끼리 합치면 정답이 된다. 예를 들어 i = 5일 때 map[5]에 들어있는 숫자가 5라도 이것은 사이클이 발생한 것이다.
주어진 정수들이 3, 1, 1, 5, 5, 4, 6일 때 tempVisited와 map은 다음과 같다.
이런 식으로 i=7까지 반복하면 된다.
visited가 true인 것들이 정답이다.
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int n;
cin >> n;
map<int, int> m;
int temp;
for (int i = 1; i <= n; i++) {
cin >> temp;
m[i] = temp;
}
vector<int> answer;
vector<int> real;
vector<bool> visited(n + 1, false);
for (int i = 1; i <= n; i++) {
vector<bool> tempVisited(n + 1, false);
int key = i;
answer.clear();
if (!visited[i]) {
while (true) {
tempVisited[key] = true;
key = m[key];
answer.push_back(key);
if (tempVisited[key]) {
if (key != i) {
answer.clear();
}
break;
}
}
}
for (int i = 0; i < answer.size(); i++) {
int index = answer[i];
visited[index] = true;
}
}
for (int i = 1; i <= n; i++) {
if (visited[i]) {
real.push_back(i);
}
}
sort(real.begin(), real.end());
cout << real.size() << '\n';
for (int i = 0; i < real.size(); i++) {
cout << real[i] << '\n';
}
return 0;
}
for문 안에서의 방문했는지 아닌지는 tempVisited에 저장했고 전체에서 방문했는지 아닌지 즉 정답을 체크하는 것은 visited에 저장했다.
