[백준/BOJ] 백준 15462번 : The Bovine Shuffle

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

15462번: The Bovine Shuffle

 

셔플이 몇 번 이루어지더라도 항상 소가 있는 위치의 개수를 찾는 문제이다. 각 위치에서 셔플이 일어나서 이동하는 위치로 연결되는 그래프를 만들고, 해당 그래프에 존재하는 사이클에 포함된 노드의 개수를 구해서 문제를 해결했다.

 

사이클을 판별하는 방법은, SCC를 이용했다.

 

코드

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

//셔플이 몇번 이루어지더라도 항상 소가 있는 위치의 개수 찾기

int n;
int adj[100005];
int visited[100005];

int result = 0;

//scc를 이용하여 사이클 집합을 구한다
int node_cnt = 0;
stack<int> st;
int node_id[100005];
int scc_maked[100005];

int dfs(int here) {
	visited[here] = 1;

	node_cnt++;
	node_id[here] = node_cnt;

	int parent = node_id[here];
	st.push(here);

	int there = adj[here];

	if (visited[there] == 0) {
		parent = min(parent, dfs(there));
	}

	else if (scc_maked[there] == 0) {
		parent = min(parent, node_id[there]);
	}

	if (parent == node_id[here]) {

		int scc_size = 0;

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

			scc_maked[st_top] = 1;
			scc_size++;

			if (st_top == here) {
				break;
			}
		}

		if (scc_size > 1) {
			result += scc_size;
		}

		else if (scc_size == 1) {
			//자기 자신 사이클일때
			if (adj[here] == here) {
				result += 1;
			}
		}
	}

	return parent;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 1; i <= n; i++) {
		int a;
		cin >> a;

		adj[i] = a;
	}

	//사이클을 모두 구하고 각 사이클에 포함되는 정점의 개수를 모두 구한다
	for (int i = 1; i <= n; i++) {

		if (visited[i] == 1) { //이미 방문 했을때
			continue;
		}

		dfs(i);
	}

	cout << result;

	return 0;
}