[BOJ] 백준 10451 순열 사이클

[BOJ] 백준 10451 순열 사이클

문제 링크 : https://www.acmicpc.net/problem/10451

DFS와 BFS 문제 2 입니다.

저는 이 문제가 연결된 영역 색칠하기와 비슷한 유형이라고 생각합니다.

각각 독립적인 왕국을 동화책에 색칠하는 유형 입니다.

각 정점들은 1~n 의 index가 붙습니다. 따라서 DFS를 사용하였을 때 그냥 원소는 하나 이므로, 리스트를 사용하였습니다.

방문이 안된 index의 첫번째 원소를 계속 탐색하면 되는 문제 입니다.

소스 코드 : 

#include 
#include 
#include 
using namespace std;


vector v[1001];
bool visited[1001] = { false, };

void DFS(int idx) {
        // 방문 안된 index일 경우, 첫번째 원소를 재탐색(DFS)한다.
 if (visited[idx]==false) {
  visited[idx] = true;
  DFS(v[idx][0]);
 }
}


int main() {
 int T;
 cin >> T; cin.ignore();
 for (int tcase = 0; tcase < T; tcase++) {

  int size;
  cin >> size; cin.ignore();


  for (int i = 1; i <= size; i++) {
   int a; cin >> a;
   v[i].push_back(a);
  }
  int color = 0;
  for (int i = 1; i <= size; i++) {
   if (visited[i] == false) {
    
    DFS(i);
                                // 다른 영역일경우 색칠한다.
    color++;
   }
  }
  cout << color << endl;
  memset(visited, false, 1001);
  for (int i = 1; i <= size; i++) {
   v[i].clear();
  }
 }
}