dfs를 이용한 문제이다. 기존 dfs와 다른 점이라면 조건을 만족할 때 지나온 값들을 모두 정렬하여 출력해야 한다는 점이다. 그래서 중복을 제거해주고 정렬을 해주는 set
을 이용했다. 1부터 N까지 반복문을 돌면서 dfs
를 해준다. dfs
를 하면서 지나온 값들을 set<int> tmp
에 넣어주고 visit
이 true
인 지점에 도달했을 때 start
, 즉 시작 지점에 도달했다면 이를 전역 변수인 set<int> res
에 저장해주었다. 이를 반복해주며 res
값들을 구해 출력해주었다. 어렵지 않게 풀 수 있었다.
#include <iostream>
#include <vector>
#include <set>
#include <cstring>
using namespace std;
int N;
vector<int> v;
set<int> res;
bool visit[101];
void dfs(int start, int next, set<int> tmp) {
if (visit[next]) {
if (start == next) {
res.insert(tmp.begin(), tmp.end());
}
return;
}
visit[next] = true;
tmp.insert(next);
dfs(start, v[next], tmp);
}
void solution() {
for (int i = 1; i <= N; i++) {
visit[i] = true;
dfs(i, v[i], { i });
memset(visit, false, sizeof(visit));
}
cout << res.size() << endl;
for (auto elem : res) {
cout << elem << endl;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
int a;
v.push_back(-1);
for (int i = 0; i < N; i++) {
cin >> a;
v.push_back(a);
}
solution();
return 0;
}