BOJ 31409 착신 전환 소동

문제 링크입니다.

f(전화기) = 다른 전화기

각 전화기의 착신 전환 관계를 전화기에서 전화기로 가는 함수로 생각할 수 있습니다. 그렇다면 전화기를 정점으로, 전화기 사이의 착신 전환을 방향 있는 간선으로 나타냈을 때, 그래프는 함수형 그래프가 됩니다. 함수형 그래프는 모두 사이클과 그 사이클로 들어가는 트리형 경로로 구성됩니다.

그러니까 어떤 전화기를 먹통으로 만들고 싶다면, 크기가 2 이상인 사이클이 존재한다면 거기에 바로 붙여주면 되고, 없다면 다른 전화기와 사이클을 만들어 주면 됩니다.

현재 상황에서 착신이 잘 되는 전화기만 사이클로 붙여주면 원래 그 전화기로 착신 전환이 일어나던 전화기까지 모두 먹통이 됩니다. 그러므로, 우리는 그냥 지금 당장 착신 전환이 없는 전화기를 모두 찾아 다른 적당한 전화기로 착신 전환을 걸어주는 것으로 모든 전화기를 먹통으로 만들어 버릴 수 있습니다!

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int a[123456], ans;
int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int n; cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		if(a[i] == i){
			ans++;
			a[i] = 1+(i==1);
		}
	}
	cout << ans << '\n';
	for(int i = 1; i <= n; i++) cout << a[i] << ' ';
}