[백준] 10451 : 순열 사이클, 순열 그래프

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

10451번: 순열 사이클

 

순열

서로 다른 N개의 원소를 일렬로 나열

순열 그래프

순열을 그래프로 표현한 것

- 각 노드는 단 하나의 다른 노드로만 연결된다 + 단일 방향

- 모든 노드는 하나 이상의 사이클을 형성한다.

 

틀린 이유

맞췄다고 생각했는데 자꾸 틀렸다.. 4%대에서 틀렸는데, 이렇게 초반에 틀릴 경우 출력 형식을 확인해보아야한다.

출력시 줄 바꿈을 하지 않아서 틀린 거였다.. 허허

 

코드

#include <bits/stdc++.h>
using namespace std;
int t, n, e, cnt, firstNode;
vector<int> graph[1004];
int visited[1004];

void dfs(int here){
    visited[here]=1;
    for (int node: graph[here]){
        if (!visited[node]) {
            dfs(node);
        }
    }
}
int main(){
    //1. 입력하기
    cin >> t;
    while (t--){
        cin >> n;
        for (int i=1;i<=n;i++){
            cin >> e;
            graph[i].push_back(e);
        }
        //2. dfs 수행
        for (int i=1;i<=n;i++){
            if (!visited[i]){
                firstNode = i;
                dfs(i);
                cnt++;
            }
        }
         //3. 정답 출력
        cout << cnt << "\n";
        //4. 초기화
        fill(visited, visited+1004, 0);
        for(auto &v: graph){
            v.clear();
        }
        cnt = 0;
    }   
}