[BOJ] 9466번 : 텀 프로젝트

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

9466번: 텀 프로젝트

---

풀이

일단, 문제를 다음과 같이 해석할 수 있다.

(인덱스 → 선택된 학생의 번호) 의 간선들로 이루어진 그래프에서 사이클을 구성하지 않는 정점의 개수를 구하라.

 

https://yunny-world.tistory.com/56

[BOJ] 11581번 : 구호물자

방향 그래프에서 사이클을 찾아야 하기 때문에, 위 문제와 동일한 방법으로 해결 가능하다.

 

프로젝트 팀에 속하지 못한 학생들의 수 = 전체 학생 수 - 프로젝트 팀에 속한 학생들의 수

이기 때문에 '프로젝트 팀에 속한 학생들의 수', 즉, '사이클 내 정점의 개수'를 구하면 답을 구할 수 있다.

'len[i] = i번 정점까지 이어진 정점들의 개수'를 관리하여 구할 수 있다.

---

코드

ll n, haveTeam;
ll v[100005];
ll g[100005];
ll len[100005];

void dfs(ll x, ll p)
{
	if (v[x] == 1)
	{
		haveTeam += len[p] - len[x] + 1;
		return;
	}
	len[x] = len[p] + 1;
	v[x] = 1;
	if (v[g[x]] != 2) dfs(g[x], x);
	v[x] = 2;
}

void solve()
{
	haveTeam = 0;
	memset(v, 0, sizeof(v));
	memset(len , 0, sizeof(len));
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> g[i];
	for (int i = 1; i <= n; i++) 
		if (!v[i])
		{
			len[i] = 1;
			dfs(i, 0);
		}
	cout << n - haveTeam << '\n';
}