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

이진중·2022년 5월 30일
0

알고리즘

목록 보기
39/76

순열 사이클


문제풀이

  1. dfs를 이용해서 탐색을하고 cnt를 하나씩 올리면 된다.

코드 작성시

코드 작성중 reset()를 작성할때 graph배열의 인덱스를 1부터 n까지쓰므로
초기화할때도 1부터 n까지 다 초기화를 해줘야한다.
나는 실수로 0~n까지 초기화를 시켰다.

for(auto w : graph[v])

벡터에서 반복문을 쓸때 자주 사용되는 방식의 문법이다.
graph[v]의 원소들을 하나씩 w에 대입시켜서 반복시킨다는 말이다.
graph[v] = {3,4,5}라면,
처음돌때는 w=3
두번째는 w=4
마지막은 w=5가 되는것이다.

실제 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <string>
#include <string.h>
#include <queue>
using namespace std;
#define endl "\n"


#define MAX 1000+1
int t, n;
vector<int> graph[MAX];
bool visited[MAX];

void reset() {
	for (int i = 1; i <= n; i++)
	{
		graph[i].clear();
		visited[i] = false;
	}
}

void dfs(int v) {
	visited[v] = true;

	for (auto w : graph[v]) {
		
		if (!visited[w])
		{
			dfs(w);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//ifstream cin; cin.open("input.txt");

	cin >> t;

	while (t--)
	{
		cin >> n;
		reset();
	
		for (int i = 1; i <= n; i++)
		{
			int tmp;
			cin >> tmp;
			graph[i].push_back(tmp);
		}

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

0개의 댓글