[C++] 백준 10451: 순열 사이클

문제

[C++] 백준 10451: 순열 사이클 SILVER 3
https://www.acmicpc.net/problem/10451

 

---

 

접근 방법

이 문제는 순열이 주어졌을 때, 그 순열에 포함된 사이클의 개수를 구하는 문제이다.
각 숫자는 정확히 하나의 숫자를 가리키므로, 전체 구조는 방향 그래프이며 각 연결 요소는 반드시 하나의 사이클을 포함한다.

 

그래프를 graph[i] = 다음 정점 형태로 저장한 뒤,
아직 방문하지 않은 정점에서 DFS를 시작하면 하나의 사이클을 전부 탐색할 수 있다.
따라서 DFS를 한 번 시작할 때마다 사이클의 개수를 1 증가시키면 된다. (cnt++)

 

구현 시 주의할 점

• 이 문제는 일반 그래프가 아니라 순열 그래프이므로,
  한 정점에서 갈 수 있는 다음 정점이 항상 하나뿐이라는 점을 이용하면 DFS가 매우 단순해진다.
• 각 케이스가 끝날 때마다 visited와 graph를 초기화해야 한다.

 

---

 

코드

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

int n;
vector<int> graph;
vector<bool> visited;

void dfs(int start)
{	
	if (visited[start] == false)
	{
		visited[start] = true;
		dfs(graph[start]);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int test_case = 0;
	cin >> test_case;

	for (int t = 1; t <= test_case; t++)
	{
		cin >> n;
		graph.resize(n + 1, 0);
		visited.resize(n + 1, false);

		for (int i = 1; i <= n; i++)
			cin >> graph[i];

		int cnt = 0;
		for (int i = 1; i <= n; i++)
		{
			if (visited[graph[i]] == false)
			{
				dfs(graph[i]);

				cnt++;
			}
		}
		cout << cnt << '\n';

		visited.clear();
		graph.clear();
	}
	return 0;
}