[C++] 백준 - 10451 : 순열 사이클

문제 링크

10451번: 순열 사이클

풀이 ) 

  vector를 사용했다.

  첫번째 원소를 시작으로 다음 원소를 방문한 다음에 해당 원소가 사용된 적이 있으면 사이클이 생성된 것이기 때문에 다음 다음 원소로 시작하는 사이클을 찾는다.

 

#include <cstdio>
#include <vector>
using namespace std;

int main(void)
{
  int t;
  scanf("%d", &t);
  while(t--){
    int n, input, ans = 0;
    vector<int> v;
    vector<int> used;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
      scanf("%d", &input);
      v.push_back(input);
      used.push_back(0);
    }

    for(int i = 0; i < n; ++i){
      if(used[i]){
        continue;
      }
      used[i]++;
      ans++;
      int next = v[i];
      while(!used[next-1]){
        used[next-1]++;
        next = v[next-1];
      }
    }
    printf("%d\n", ans);
  }
}