[C++] BOJ 10451 순열사이클

 

 

문제 출처

백준 온라인 저지

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

10451번: 순열 사이클

 

문제 

 

입 / 출력

 

풀이

우선 정수들을 순서대로 배열에 입력한 뒤,

DFS 알고리즘을 사용해서, DFS 함수를 호출할 때마다 cnt값을 증가시키며 사이클의 개수를 구한다. 

 

코드

#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

const int MAX = 1001;
int T, N, result, cnt = 0;
int graph[MAX];
bool visited[MAX];

void cycle(int start) {
  visited[start] = true;
  if (!visited[graph[start]]) {
    cycle(graph[start]);
  }
}

int main() {
  cin >> T;
  for (int i = 0; i < T; i++) {
    cnt = 0;
    cin >> N;
    for (int j = 1; j <= N; j++) {
      cin >> graph[j];
    }
    for (int j = 1; j <= N; j++) {
      if (!visited[j]) {
        cycle(j);
        cnt++;
      }
    }
    cout << cnt << "\n";
    memset(visited, false, sizeof(visited));
  }
}