I번은 쉬운 문제 (백준 20504)

안녕하세요. 오늘은 I번을 풀어볼 거예요.

문제

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

아이디어

이 문제는 SCC로 풀 수 있습니다.

테스트 케이스를 신경쓰지 말고 생각해봅시다.
indegree가 0인 그룹의 수가 정답이 됩니다.
즉, 자신에게 오는것이 없는 그룹을 뜻합니다.

간단히 증명을 하자면
1. 만약 어떤 그룹에서 시작을 한다고 해봅시다.
2. 그 그룹이 의미가 있으려면 그 그룹으로 가는 그룹이 선택이 되지 말아야합니다.
3. 그런데 그러면 그 그룹은 아무도 선택을 못해줍니다.
4. 그러므로 이왕이면 그룹을 선택하지 말고 선택을 한다면 indegree가 0인 그룹을 선택을 해야합니다.

indegree가 0인 그룹을 모두 선택해야합니다.

그러므로 테스트 케이스에 indegree가 0인 그룹이 모두 포함되어있으면, 즉, indegree가 0인 모든 그룹에 대해 테스트케이스에 그 그룹에 포함되어있는 정점이 하나이상 존재한다면, indegree가 0인 그룹의 수를 출력해주면 됩니다.

그런 경우가 아니라면 -1을 출력해야합니다.

소스코드

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

vector <int> v1[202020], v2[202020]; //정방향, 역방향
bool visited[202020] = { 0 };
stack <int> s;
vector <int> scc;

void dfs1(int node)
{
	visited[node] = true;
	for (int next : v1[node])
		if (visited[next] == false)
			dfs1(next);
	s.push(node);
}
void dfs2(int node)
{
	visited[node] = true;
	scc.push_back(node);
	for (int next : v2[node])
		if (visited[next] == false)
			dfs2(next);
}

int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N, M, i, a, b;
	cin >> N >> M;
	for (i = 0; i < M; i++)
	{
		cin >> a >> b;
		v1[a].push_back(b);
		v2[b].push_back(a);
	}
	for (i = 1; i <= N; i++)
		if (visited[i] == false)
			dfs1(i);
	for (i = 1; i <= N; i++) visited[i] = false;

	int GroupNum[202020] = { 0 };
	int idx = 0;
	while (s.size())
	{
		int node = s.top();
		s.pop();
		if (visited[node]) continue;
		dfs2(node);
		idx++;
		for (int now : scc)
			GroupNum[now] = idx; //그룹번호 부여
		scc.clear();
	}

	int indegree[202020] = { 0 }; //그룹별 indegree: 안으로 들어오는 간선의 수
	for (i = 1; i <= N; i++)
	{
		int from = i;
		for (int to : v1[from])
		{
			if (GroupNum[from] != GroupNum[to])
				indegree[GroupNum[to]]++;
		}
	}

	int cnt = 0;
	for (i = 1; i <= idx; i++)
		if (indegree[i] == 0)
			cnt++;

	int T, x;
	bool can_start[202020] = { 0 };
	cin >> T;
	for (i = 0; i < T; i++)
	{
		cin >> x;
		can_start[GroupNum[x]] = true; //갈 수 있음
	}

	for (i = 1; i <= idx; i++)
	{
		if (indegree[i] == 0 && can_start[i] == false) //indegree는 0인데 시작은 못한다?
		{
			cout << -1; //불가능
			return 0;
		}
	}

	cout << cnt; //아니면 indegree가 0인 그룹의 개수
}

감사합니다!!