[C++/백준] 9466 텀 프로젝트

#9466 텀 프로젝트
https://www.acmicpc.net/problem/9466

📝문제 포인트

사이클을 이루는 그래프에 한해서만 팀이 될 수 있다. (개인도 팀이 될 수 있음). 결론적으로 전체 '명수 - 사이클을 이루는 그래프의 개수'를 출력하면 된다.....

🤦‍♀️사이클을 이루는지는 어떻게 아나..?

사이클이 생긴다는 건 한 번 방문했지만 또 방문한다는 이야기이다.

4-7-6-(4)라면 사이클이 존재하는 그래프이다.
4는 이미 방문되었지만 6의 다음으로써 또 dfs(4)가 호출된다면,
사이클이 생기게 된다 !!!! 그걸 체크해줄 배열이 done이다.
4부터 6까지 몇 개의 노드가 있는 지 센다. 고거시 사이클을 이루는 노드들의 개수...

✍코드

#include <iostream>
#include <string.h>
#define MAX 100001
using namespace std;

bool visited[MAX];
bool done[MAX];
int map[MAX]; 
int cnt = 0;

void dfs(int v) {
	visited[v] = true;
	int next = map[v];
	
	if (!visited[next]) {
		dfs(next);
	}
	else {
		if (!done[next]) {
			for (int i = next; i != v; i = map[i]) cnt++;
			cnt++;
		}
	}
	done[v] = true;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int n,test;
	cin >> test;
	for(int i=0;i<test;i++) {
		cin >> n;
		cnt = 0;
		memset(visited, false, sizeof(visited));
		memset(done, false, sizeof(done));
		memset(map, 0, sizeof(map));

		for (int i = 1; i <= n; i++) {
			cin >> map[i];
		}
		for (int i = 1; i <= n; i++) {
			if (!visited[i]) {
				dfs(i);
			}
		}
		cout << n - cnt<<'\n';
	}
}

그래프 너란 녀석...정말 어렵다...🤦‍♀️