[Backjoon] 순열 사이클

쉬운 그래프 문제 중 하나였다. 기본적인 개념을 복습하기 좋게 문제가 설계되어 있었다. 방향 그래프에 대한 개념과 그래프 순회방법을 복습했다. 해당 문제는 인접리스트를 쓸 필요가 없는데 인접 노드가 하나로 고정되어 있기 때문이다. 아래는 소스코드이다.

 

#include <iostream>
#include <string.h>
#include <queue>

using namespace std;

int graph[1001];
bool visited[1001];

void bfs(int start) {
    queue<int> q;
    q.push(graph[start]);
    visited[start] = true;

    while (!q.empty()) {
        int now = q.front();
        q.pop();

        if (!visited[now]) {
            visited[now] = true;
            q.push(graph[now]);
        }
    }
}

int main() {

    int caseCount;
    cin >> caseCount;

    while (caseCount--) {
        int size;
        cin >> size;

        for (int i = 1; i <= size; ++i) {
            cin >> graph[i];
        }

        int cycleCount = 0;
        for (int node = 1; node <= size; ++node) {
            if (!visited[node]) {
                bfs(node);
                cycleCount++;
            }
        }

        cout << cycleCount << endl;

        memset(graph, 0, 1001 * sizeof(int));
        memset(visited, false, 1001 * sizeof(bool));
    }

    return 0;
}