백준 10451. 순열 사이클

www.acmicpc.net/problem/10451

10451번: 순열 사이클

다시푼문제, 이전글: tose33.tistory.com/6

 

vector에 간선정보 저장, dfs는 스택이용해서 푼것

#include <iostream>
using namespace std;
#include <vector>
#include <stack>
#include <cstring>

vector<int> edge[1002];
bool mark[1002];

void dfs(int n){
    stack<int> s;
    s.push(n);
    mark[n] = true;

    while(!s.empty()) {
        int f = s.top();
        bool none = true;
        for(int x : edge[f]) {
            if(!mark[x]) {
                mark[x] = true;
                s.push(x);

                none = false;
                break;
            }
        }
        if(none) s.pop();
    }
}

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n; // 순열의 크기

        memset(mark, false, sizeof(mark));

        for (int i = 1; i <= n; i++) {
            edge[i].clear();
            int a;
            cin >> a;
            edge[i].push_back(a);
        }


        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (!mark[i]) {
                dfs(i);
                cnt++;
            }
        }
        cout << cnt << endl;
    }
}

 

배열에 간선정보 저장, dfs 재귀 이용해 푼것

#include <iostream>
using namespace std;

bool mark[1002];
int arr[1002];

void dfs(int n) {
    if(mark[n]) return;
    mark[n] = true;

    dfs(arr[n]);
}

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;

        for(int i = 1; i <= n; i++) {
            mark[i] = false;

            cin >> arr[i];
        }
        int cnt = 0;
        for(int i = 1; i <= n; i++) {
            if(!mark[i]) {
                dfs(i);
                cnt++;
            }
        }
        cout << cnt << endl;
    }
}

이 문제 같은 경우에는 하나의 정점에 간선이 무조건 하나이므로 2차원 벡터(배열)가 아닌 그냥 1차원 배열로 풀어도 된다.

 

 

 

여러개의 테스트케이스로 이루어진 문제에서

배열 등을 전역변수로 선언 했을때 초기화 해주는 것을 잊지말자.