Study with book/Algorithms

[백준]순열 사이클


백준저지

[순열 사이클]https://www.acmicpc.net/problem/10451

이 문제는 몇 개의 사이클이 존재하는지를 출력해야 한다.

문제 이해는 쉽게 되었고 시간도 얼마 걸리지 않았다.

구현

- 먼저 입력 받은 정점의 개수 + 1만큼 intvector타입 vec변수

- 방문 여부를 나타내는 visitArr배열을 선언했다. (index와 값을 맞추기 위함)

- jindex를 나타내고 vec[j]정점에 연결된 다른 정점을 뜻함

 

- 21 line: 정점의 개수만큼 반복한다.

- 22 line: 선택된 정점이 방문되지 않았다면,

- 23 line: visit 변수선택된 정점(j)으로 초기화하고

- 24 line: 아래 내용을 반복하는데,

- 25 line: 선택된 정점방문하고(true로 초기화)

- 26 line: 선택된 정점과 연결된 정점이 같다면,

- 27 line: 사이클 수를 증가하고

- 28 line: while(1)문을 빠져나가for문을 실행한다.

- 29 line: 선택된 정점과 연결된 정점이 같지 않다면,

- 30 line: visit변수선택된 정점에 연결된 정점으로 초기화 한다.

#include <iostream>
#include <vector>

using namespace std;

int main(void) {
	int num;
	cin >> num;
	for (int i = 0; i < num; i++) {
		int cnt; int cycleCnt = 0;
		cin >> cnt;

		vector vec(cnt + 1, 0);
		bool * visitArr = (bool *)malloc(sizeof(bool)*(cnt + 1));

		for (int j = 1; j < cnt + 1; j++) {
			cin >> vec[j];
			visitArr[j] = false;
		}

		for (int j = 1; j < cnt + 1; j++) {
			if (visitArr[j] != true) {
				int visit = j;
				while (1) {
					visitArr[visit] = true;
					if (j == vec[visit]) {
						cycleCnt++;
						break;
					} else {
						visit = vec[visit];
					}
				}
			}
		}
		cout << cycleCnt << endl;
		free(visitArr);
	}
	return 0;
}

'Study with book > Algorithms' 카테고리의 다른 글

[백준]2xn 타일링2  (0) 2016.12.23
[백준]2xn 타일링  (0) 2016.12.23
[백준]DFS와 BFS3  (0) 2016.12.22
[백준]DFS와 BFS2  (0) 2016.12.22
[백준]DFS와 BFS1  (0) 2016.12.22