(c++)백준 10451번: 순열 사이클

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

10451번: 순열 사이클

[풀이]

bfs를 이용하여 풀었다. 이어진 정점을 방문하다가 처음 시작했던 정점이 나오면 순열 사이클이므로 개수를 갱신해 주었다.

 

#include <iostream>
#include <queue>
#include <cstring>//memset
using namespace std;

int T, N;
int P[1001];//순열 저장
bool check[1001];//방문한 정점은 true;

bool bfs(int start) {
	queue<int>q;
	q.push(start);
	check[start] = true;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		int next = P[cur];
		//순열 사이클이면 true 반환
		if (next == start)
			return true;
		check[next] = true;
		q.push(next);
	}
	return false;
}

void solution() {
	cin >> T;
	while (T--) {
		cin >> N;
		int cnt = 0;
		for (int i = 1; i <= N; i++) {
			cin >> P[i];
		}
		for (int i = 1; i <= N; i++) {
			if (check[i] == false) {
				if (bfs(i))
					cnt++;
			}
		}
		cout << cnt << endl;

		//check 초기화
		memset(check, false, sizeof(check));
	}
}

int main() {
	solution();
	return 0;
}