[BOJ] 11581번 : 구호물자

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

11581번: 구호물자

---

풀이

1번에서 DFS를 시작해서 사이클이 있는지 판단하면 된다.

이때, 정점을 3가지 상태로 표현해서 구현을 해야 한다.

vi[i]의 값이

0일때, 아직 정점을 방문하지 않았다.

1일때, 정점을 방문 중이다.

2일때, 정점을 방문 완료했다.

정점을 방문 완료한 이후에는, 더이상 그 정점을 방문할 필요가 없다.

정점을 방문 중에, 그 정점이 호출되면 사이클이 존재한다.

---

코드

ll n;
vector<ll> g[105];
ll vi[105];

void dfs(ll now)
{
	if (vi[now] == 1)
	{
		cout << "CYCLE";
		exit(0);
	}
	vi[now] = 1;
	for (auto nxt : g[now]) if (vi[now] != 2) dfs(nxt);
	vi[now] = 2;
}

void solve()
{
	cin >> n;
	for (ll i = 1; i < n; i++)
	{
		ll m; cin >> m;
		for (ll j = 0; j < m; j++)
		{
			ll c; cin >> c;
			g[i].push_back(c);
		}
	}
	dfs(1);
	cout << "NO CYCLE";
}

---

이 문제를 통해서 사이클을 판단해야 할 때, 무방향 그래프에선 분리 집합, 방향 그래프에선 세 가지 상태를 가진 DFS를 떠올려야 함을 배우게 되었다.