[백준] 10451번. 순열 사이클 (C++)

문제설명

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

10451번: 순열 사이클

해결방법

쉬운문제이다

 

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


bool DFS(int vertex, vector<vector<int>>& graph, vector<int>& isStart)
{
	while (1)
	{
		int next = graph[vertex][0];
		if (isStart[next] == 1) { return true; }
		else if (isStart[next] == 2) { return false; }
		else if (isStart[next] == 0) { isStart[next] = 2; vertex = next; }
	}
}


void test() 
{
	int size;
	cin >> size;

	vector<vector<int>> graph  (size + 1);
	vector<int> isStart(size + 1, 0);
	//0=방문하지 않았다 1=시작점이다 2=시작점이 아니다
	

	for (int i = 1; i <= size; i++) 
	{
		int input;
		cin >> input;

		graph[i].push_back(input);
	}


	int count = 0;
	for (int i = 1; i <= size; i++)
	{
		if (isStart[i] == 0) 
		{ 
			isStart[i] = 1;
			if (DFS(i,graph,isStart) == true) { count++; } 
		}

	}
	
	cout << count << "\n";

}



int main() {

	int T;
	cin >> T;
	for (int i = 0; i < T; i++) { test(); }

}

 

1. test 함수

 

int size; cin >> size;
순열의 사이즈를 입력받는다

vector<vector<int>> graph  (size + 1);

vector<int> isStart(size + 1, 0);
isStart함수는 정점별 정보를 나타낸다.

0=방문하지 않았다 1=시작점이다 2=시작점이 아니고 방문한적이있다.

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


int count = 0;
for (int i = 1; i <= size; i++)
{
if (isStart[i] == 0) 
{ 
isStart[i] = 1;
if (DFS(i,graph,isStart) == true) { count++; } 
}

}

cout << count << "\n";

 

 

 

2. DFS 함수

bool DFS(int vertex, vector<vector<int>>& graph, vector<int>& isStart)
{
while (1)
{
int next = graph[vertex][0];
if (isStart[next] == 1) { return true; }
else if (isStart[next] == 2) { return false; }
else if (isStart[next] == 0) { isStart[next] = 2; vertex = next; }
}
}