[BAE/<JOON> 문제풀이] 9466. 텀 프로젝트

www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

풀이::

1차 탐색에서 요소들에 1표시를 하고 스택에 넣으며 중복되는 지점을 찾는다.

 

중복 지점(1표시)을 찾으면 해당 인덱스가 나올 때 까지 스택을 POP 시키며 요소들에 2표시를 하고 갯수를 셈

 

만약 1표시를 찾기전에 2표시를 찾으면 해당 탐색 종료(이미 탐색된 루트임)

 

스택에 남은 요소들도 모두 2표시를 하고 다음 탐색되지 않은 인덱스 탐색

 

1표시 : 1차 루프 탐색

 

2표시 : 탐색 완료 표시

#include <iostream>
#include <vector>
#include <stack>

using namespace std;
int arr[100001];
int ch[100001];
int val = 0;

int main()
{
	int tc;
	cin >> tc;
	while (tc--) {
		val = 0;
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> arr[i];
			ch[i] = 0;
		}

		for (int i = 1; i <= n; i++) {
			if (ch[i] > 0) {
				continue;
			}
			int current = i;
			stack<int> st;
			while (ch[current] != 2) {
				if (ch[current] == 1) {
					val++;
					while (st.top() != current) {
						val++;
						ch[st.top()] = 2;
						st.pop();
					}
					while (!st.empty()) {
						ch[st.top()] = 2;
						st.pop();
					}
					break; 
				}
				st.push(current);
				ch[current] = 1;
				current = arr[current];
			}
			while (!st.empty()) {
				ch[st.top()] = 2;
				st.pop();
			}
		}

		cout << n - val << "\n";
	}

	return 0;
}