백준 온라인 저지 10451 번 순열사이클
문제
1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 와 같다.
순열을 배열을 이용해 로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.
순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 “순열 사이클” 이라고 한다.
N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N (2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.
출력
각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다
백준 온라인 저지
소스코드
#include <iostream>
#include <vector>
using namespace std;
void dfs(int start, vector<int>* graph, bool* check,int& cnt){
if (check[start]){//이미 방문했던곳이라면 리턴
return;
}
check[start] = true;
int next = graph[start][0]; // 다음 방문장소 지정
if (!check[next])
dfs(next, graph, check, cnt);
else
cnt++;// 다음방문장소가 체크되어있다면 카운트++
}
int main(){
int testNum, nodeNum;
cin >> testNum;
while (testNum > 0){
cin >> nodeNum;
bool* checkArr = new bool[nodeNum + 1];
fill(checkArr, checkArr + nodeNum + 1, false);
vector<int>* graphList = new vector<int>[nodeNum+1];
for (int i = 1; i <= nodeNum; i++){
int tmp;
cin >> tmp;
graphList[i].push_back(tmp);
}
int cnt = 0;
for (int i = 1; i <= nodeNum; i++)
dfs(i, graphList, checkArr, cnt);
cout << cnt << endl;
testNum--;
}
}
문제의 핵심은 언제 카운트를 세는가이다.
