백준 알고리즘 10451번 - 순열 사이클

사이클을 구하는 문제이다.

문제에는 나와있지 않지만, 문제에 주어진 그림을 살펴보면 단방향 그래프 인것을 알 수 있다.

dfs를 구현해서, 이미 방문했다면 이미 사이클 여부를 확인한 것이므로 return 하고, 방문하지 않았다면

dfs 탐색하도록 구현 하였다.

 

소스코드

 

#include <iostream>
#include <vector>
#include <cstdio>

#define MAX 1002

using namespace std;

vector<int> graph[MAX];
int num;
int visited[MAX];

//초기화 해주는 함수
void init()
{
	for(int i=1;i<=MAX;i++) {
		visited[i]=false;
		graph[i].clear();
	}
}
//dfs를 돌린다.
void dfs(int start)
{
	visited[start]=true;
	for(int i=0;i<graph[start].size();i++){
		int next=graph[start][i];
		if(!visited[next]){
			dfs(next);
		} 
	}
}

int main()
{
	int test;
	cin>>test;

	//test 횟수 입력받아 그만큼 돌림
	for(int i=0;i<test;i++){
		init();
		int count=0;
		scanf("%d",&num);
		//각각 그래프를 vector로 구현
		for(int j=1;j<=num;j++){
			int a;
			scanf("%d",&a);
			graph[j].push_back(a);
		}
		//사이클 안돌은걸 발견할 때마다 dfs돌린다
		for(int j=1;j<=num;j++){
			if(!visited[j]){
				count++;
				dfs(j);
			}
		}
		printf("%d\n",count);
	}
}