[백준] 골드5 : (2668) 숫자고르기

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

 

첫째 줄에서 숫자는 둘째 줄의 숫자로 이동할 수 있다는 의미를 가진다.

문제의 예시 표를 보면, 1은 3으로 이동할 수 있고, 3은 다시 1로 이동할 수 있으므로 1 <-> 3의 순한 구조가 생긴다.

2의 경우, 2는 1로 갈 수 있지만 1을 통하는 경로에서는 다시 2로 갈 수 없기 때문에 2는 집합에 끼지 못한다.

1	2	3	4	5	6	7
3	1	1	5	5	4	6

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

int main()
{
	int N;
	cin >> N;

	vector<int> Answer;						// 정답 배열 (정렬하여 작은 수 부터 출력하기 위함)
	vector<pair<int, bool>> Graph(N + 1);	// 각 번호와 그 밑의 수.
	vector<int> Visit(N + 1);				// 각 번호가 정답 배열에 포함되었는지 확인.

	for (int i = 1; i <= N; ++i)
		cin >> Graph[i].first;

	for (int i = 1; i <= N; ++i)
	{
		// 이미 정답 배열에 포함된 번호이면 패스.
		if (Graph[i].second) continue;

		vector<bool> Visit(N + 1); // 순환 구조를 해결할 방문 체크.
		vector<int> Save; // 정답 배열에 추가할 번호 배열.

		// 시작 번호
		int CurValue = i;

		// 현재 정수에서 시작하여 순환 구조를 찾음.
		while (true)
		{
			// 순환이 발생했는지 확인
			if (Visit[CurValue]) break;

			Visit[CurValue] = true;
			Save.push_back(CurValue);

			CurValue = Graph[CurValue].first;
		}

		// 추적이 끝났을 떄, 처음 시작한 번호와 동일한지 확인. (동일하면 순환된다는 의미)
		if (CurValue == i)
		{
			for (const auto& i : Save)
			{
				Answer.push_back(i);
				Graph[i].second = true;
			}
		}
	}

	// 오름차순 정렬.
	sort(Answer.begin(), Answer.end());

	cout << Answer.size() << "\n";
	for (const auto& i : Answer)
		cout << i << "\n";

	return 0;
}