[백준 2668] 숫자고르기, c++

www.acmicpc.net/problem/2668

2668번: 숫자고르기

취업 이후 오랜만에 ps 문제를 풀었다. 한 2달은 문제를 안풀었더니 다 까먹었다ㅠㅠ 취업준비 기간때는 그래도 골드2 이하 문제는 쉽게 풀었던거 같은데 이젠 실버2도 힘들다... 곧 자취를 하는데 다시 열심히 공부해야겠다.

본 문제는 KOI 1996 초등부 2번 문제로 cycle의 집합을 구하는 문제다. dfs를 이용하여 주어진 배열을 탐색하면서 cycle이 발생할 때 집합에 추가해야 한다. 이때 cycle의 중복이 있을 수 있으므로 중복을 제거하면 된다.

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
bool chk[101];
int d[101];
vector<int> ans;
 
int n;
 
void cal(int start, int cur, vector<int> vis) {
  int next = d[cur];
  
  if (!chk[next]) {
    chk[next] = true;
    vis.push_back(next);
    cal(start, next, vis);
  }
  else {
    if (start == next) {
      for (int i = 0; i < vis.size(); i++) {
        ans.push_back(vis[i]);
      }
    }
  }
}
 
int main() {
  scanf("%d", &n);
  
  for (int i = 1; i <= n; i++) {
    int tmp;
    scanf("%d", &tmp);
    
    d[i] = tmp;
  }
  
  for (int i = 1; i <= n; i++) {
    memset(chk, false, sizeof(chk));
    chk[i] = true;
    vector<int> vis;
    vis.push_back(i);
    cal(i, i, vis);
  }
  
  
  
  sort(ans.begin(), ans.end());
  
  ans.erase(unique(ans.begin(), ans. end()), ans.end());
  printf("%d\n", ans.size());
  for (int i = 0; i < ans.size(); i++) {
    printf("%d\n", ans[i]);
  }
}