Coding Test - cpp/DFS
[백준 9466: 텀 프로젝트] - C++
에드윈H
2021. 2. 19. 14:40
9466번: 텀 프로젝트
이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을
www.acmicpc.net
#include<iostream>
using namespace std;
int n = 0;
int cnt = 0;
int arr[100001];
int visited[100001];
int resultArr[100001];
void D(int curNum) {
visited[curNum] = true;
int targetNum = arr[curNum]; //현재노드가 가리키고 있는 번호
if (!visited[targetNum]) //해당 번호를 방문한적 없으면 true
{
D(targetNum);
}
else { //이미 방문해서 확인했으면 현재 번호와 연결되어 있는 노드 세기
if (!resultArr[targetNum]) //이미 노드를 셌다면 패스
{
for (int i = targetNum; i != curNum; i = arr[i]) //연결되있는 번호들 확인
{
cnt++;//연결된 점들 개수 세기
}
cnt++;//자기 자신
}
}
resultArr[curNum] = true;
}
int main()
{
int total;
cin >> total;
for (int index = 0; index < total; index++)
{
memset(arr, 0, sizeof(arr));
memset(visited, 0, sizeof(visited));
memset(resultArr, 0, sizeof(resultArr));
cnt = 0;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> arr[i];
}
for (int i = 1; i <= n; i++)
{
if (visited[i] == false)
{
D(i);
}
}
cout << n-cnt << endl;
}
return 0;
}