백준 - 9466 [C++]

 이 문제는 강한 연결 요소 (SCC) 를 이용해서 풀 수 있는 문제이다. 사실 이 문제는 dfs 를 약간만 설정해서 사이클의 판단만 해주면 풀리는 문제이다. 그러나 강한 연결 요소를 통해 유향 그래프의 사이클 요소를 찾을 수 있다는 생각이 떠올라 SCC로 풀었다.

 이 문제에서 중요한 건 입력으로 주어지는 간선은 outgoing edge가 단 하나라고 명시되어 있지만, transpose graph 에서는 outgoing edge 가 하나가 아니라는 것이다. 그 사실을 망각하고 풀어서 많은 시간을 쏟게 되었다.

 

 

 

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

vector<int> edges;
vector<vector<int>> transEdges;
vector<bool> visited;
vector<int> tempScc;
vector<vector<int>> scc;
stack<int> st;

void dfs(int start)
{
	int next;

	visited[start] = true;
	next = edges[start];

	if (!visited[next])
	{
		dfs(next);
	}

	st.push(start);
}

void transDfs(int start)
{
	int next;

	visited[start] = true;
	for (int i = 0; i < transEdges[start].size(); i++)
	{
		int next = transEdges[start][i];

		if (!visited[next])
		{
			transDfs(next);
		}
	}

	tempScc.push_back(start);
}

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

	int test_case;

	cin >> test_case;

	for (int test = 0; test < test_case; test++)
	{
		int n, answer;

		cin >> n;

		answer = n;
		visited = vector<bool>(n + 1, false);
		edges = vector<int>(n + 1, -1);
		transEdges = vector<vector<int>>(n + 1, vector<int>());
		st = stack<int>();

		for (int i = 1; i <= n; i++)
		{
			int temp;

			cin >> temp;

			edges[i] = temp;
			transEdges[temp].push_back(i);
		}

		for (int i = 1; i <= n; i++)
		{
			if (!visited[i])
			{
				dfs(i);
			}
		}

		visited = vector<bool>(n + 1, false);

		while (!st.empty())
		{
			int present = st.top();
			st.pop();

			if (!visited[present])
			{
				tempScc.clear();
				transDfs(present);
				scc.push_back(tempScc);
			}
		}

		for (int i = 0; i < scc.size(); i++)
		{
			if (scc[i].size() >= 2)
			{
				answer -= scc[i].size();
			}
			else if (scc[i].size() == 1)
			{
				int temp = scc[i].front();

				if (edges[temp] == temp)
				{
					answer--;
				}
			}
		}

		cout << answer << '\n';

		scc.clear();
	}
}