[백준/C++][순열 사이클(10451번)]

문제

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

10451번: 순열 사이클

문제 풀이

1. 입력값이 주어지면 무방향 인접 리스트를 이용하여 데이터를 저장한다.

2. 인접 리스트를 모른다면 나의 블로그의 인접 리스트 포스팅을 보고 와야 한다.

3. 인접 리스트로 저장 후 DFS알고리즘을 통해 노드 1~N까지 DFS알고리즘을 돌려준다.

4. 여기서 포인트는 visit 배열과 visited 배열 두 개가 있다는 것이다.

5. visit배열은 DFS의 사용하고 visited는 사이클을 구하는 배열이다.

6. 마지막으로 결괏값을 구하고 다음 케이스로 가기 전에 반드시 초기화를 해야 한다.

 

코드

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int T,N,cnt = 0;
bool visit[1001] = {false};
bool visited[1001] = {false};
vector <int> adj[1001];
void DFS(int node){
    visit[node] = true;
    visited[node] = true;
    for(int i = 0;i<adj[node].size();i++){
        int next_node = adj[node][i];
        if(visit[next_node]){continue;}
        DFS(next_node);
    }
}
int main(void){
    cin >> T;
    for(int i = 0;i<T;i++){
        cin >> N;
        for(int j = 1;j<=N;j++){
            int a;
            cin >> a;
            adj[a].push_back(j);
            adj[j].push_back(a);
        }
        for(int k = 1;k<=N;k++){
            memset(visit,false,sizeof(visit));
            if(visited[k]){continue;}
            else{DFS(k);cnt++;visited[k] = true;}
        }
        memset(visited,false,sizeof(visited));
        cout << cnt << "\n";
        cnt = 0;
        for(int l = 0;l<=N;l++){adj[l].clear();}
    }
}