BOJ 9466 : 텀 프로젝트

 

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

9466번: 텀 프로젝트

 

문제 요약

$N$개의 정점과 $N$개의 간선으로 이루어진 방향 그래프가 주어졌을 때,
그래프에서 사이클을 이루지 않는 정점의 개수를 구하는 문제이다.

 

접근

DFS를 수행하며 사이클을 찾고, 사이클을 이루는 정점의 수를 파악해야 한다.

사이클 찾기

정점이 최대 10만 개이기 때문에 방문 여부를 저장하는 배열 visit을 선언하고,

반복문을 통해 방문하지 않은 점에 대해 1번 정점부터 N번 정점까지 DFS를 수행하며 사이클을 찾는다.

사이클을 찾을 때, 이것이 이미 찾았던 사이클인지 확인하기 위하여 visit 배열을 pair<int, int> 형으로 선언하여 visit.second값에 DFS 실행 횟수를 저장하였다.

사이클의 정점의 수 세기

DFS를 돌면서 현재 정점이 지나온 점의 개수를 새로운 배열 d에 저장해준다.

DFS함수에 지나온 점의 수를 인자로 계속 넘겨주면 구현 가능하다.

DFS중 사이클이 판별되면, (지금까지 지난 점의 개수) - (사이클의 시작점 전까지 지나온 점의 개수) 가 사이클을 이루는 점의 개수가 된다.

 

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int> > V(100001);
vector<pair<int, int> > visit(100001);
vector<int> d(100001);
int cnt = 0, idx = 0;

int dfs(int n, int p, int s) {
	visit[n] = { 1,idx };
	d[n] = s;
	for (int i : V[n]) {
		if (i == n) {
			return 1;
		}
		else if (visit[i].first && visit[i].second == idx) {
			return s - d[i] + 1;
		}
		else if (visit[i].first && visit[i].second != idx)
			return 0;
		else if (!visit[i].first) {
			return dfs(i, n, s + 1);
		}
	}
	return 0;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int T;
	cin >> T;
	while (T--) {
		int N, a;
		idx = 0;
		cin >> N;
		V = vector<vector<int> >(N + 1);
		cnt = N;
		visit = vector<pair<int, int> >(N + 1);
		d = vector<int>(N + 1);
		for (int i = 1; i <= N; i++) {
			cin >> a;
			V[i].push_back(a);
		}
		for (int i = 1; i <= N; i++) {
			if (!visit[i].first) {
				cnt -= dfs(i, 0, 1);
				idx++;
			}
		}
		cout << cnt << '\n';
	}
}