[백준 9466번] 텀 프로젝트

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

9466번: 텀 프로젝트

풀이) 

팀이 구성됐건, 안됐건 한번도 방문한 적 없는 정점을 dfs를 돌린다. 처음 시작 값을 havaTeam에 다 넣고, selected에는 개수들을 넣어둔다. 이후 어느 값이건 순환이 되어 돌아온 시점이 되면, 그 값이 처음 시작 값인 지 확인을 하고, 1 -> 2 -> 3 -> 2 와 같은 잘못된 순환은 팀이 될 수 없으므로 0을 리턴시키고, 원래 시작 값으로 돌아왔다면 팀이 정상적으로 꾸려진 것이므로 팀 인원을 반환하면 된다.

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

int T, n, ans;
int selected[100001], haveTeam[100001], wantMember[100001];
	
int dfs(int start, int dest, int cnt)
{
	if (selected[dest])
	{
		if (start != haveTeam[dest])
			return (0);
		return (cnt - selected[dest]);
	}
	haveTeam[dest] = start;
	selected[dest] = cnt;
	return (dfs(start, wantMember[dest], cnt + 1));
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> T;
	while (T--)
	{
		cin >> n;
		ans = 0;
		memset(haveTeam, 0, sizeof(haveTeam));
		memset(wantMember, 0, sizeof(wantMember));
		memset(selected, 0, sizeof(selected));
		for (int i = 1; i <= n; i++)
			cin >> wantMember[i];
		for (int i = 1; i <= n; i++)
			if (!selected[i])
				ans += dfs(i, wantMember[i], 1);
		cout << n - ans << "\n";
	}
	return (0);
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!