# [Silver III] 착신 전환 소동 [문제 링크](https://www.acmicpc.net/problem/31409) ## 문제 설명 <p>도훈이네 부대의 전화기에는 <strong>착신 전환</strong>이라는 기능이 있다. 착신 전환이란 전화기에 걸려 오는 전화를 다른 전화기로 대신 연결하는 기능이다. 가령, 전화기 $A$가 전화기 $B$로 착신 전환을 했다면, 누군가가 전화기 $A$에 전화를 걸었을 때 전화기 $B$에 전화가 걸려 오게 된다. 착신 전환은 전화기마다 최대 하나의 전화기로만 설정할 수 있다.</p> <p>그러나 해당 기능에는 큰 문제가 있는데, 착신 전환이 꼬이게 되면 일부 전화기가 먹통이 된다는 것이다! 예를 들어, 전화기 $A$가 전화기 $B$로, 전화기 $B$가 전화기 $C$로 착신 전환을 걸어 둔 상태에서 전화기 $C$가 전화기 $A$에 착신 전환을 걸어 두면 세 전화기 중 어떤 전화기에 전화를 걸어도 신호 대기 상태가 무한히 유지되며, 세 전화기 모두 먹통이 된다.</p> <p>이 사실에 깊게 감명받은 도훈이는, 일부 전화기들의 착신 전환 상태를 바꿔 부대 내의 전화기 모두를 먹통으로 만들려는 사악한 계획을 세웠다! 부대 내에는 $1$번부터 $N$번까지 총 $N$대의 전화기가 있으며, 각 전화기는 $a_i$번 전화기로 착신 전환이 되어 있는 상태이다. 만약 $a_i = i$라면, $i$번 전화기에는 착신 전환이 걸려 있지 않은 상태임을 의미한다.</p> <p>하지만 전화기들의 착신 전환 상태를 너무 많이 바꾸면 간부님께 걸릴 것이 분명하므로, 착신 전환 상태를 바꿀 전화기 개수를 최소로 해야 한다. 도훈이를 위해, 착신 전환 상태를 바꿔야 하는 최소 전화기 개수와 착신 전환 상태를 어떻게 바꿔야 하는지 구해 주자. 만약 가능한 착신 전환 상태가 여러 가지라면, 그중 아무거나 구해 주자. 모든 전화를 먹통으로 만드는 것이 항상 가능함을 증명할 수 있다.</p> ## 입력 <p>첫 번째 줄에 부대 내 전화기의 대수 $N$이 주어진다. $(2\leq N\leq 100\,000)$</p> <p>두 번째 줄에 각 전화기가 착신 전환으로 연결되어 있는 전화기의 번호를 의미하는 $N$개의 정수 $a_1,\cdots,a_N$이 공백으로 구분되어 주어진다. $(1\leq a_i\leq N)$</p> <p>이때, $a_i = i$라면 $i$번 전화기는 착신 전환이 되어 있지 않음을 의미한다.</p> ## 출력 <p>첫 번째 줄에 모든 전화를 먹통으로 만들기 위해 착신 전환 상태를 바꿔야 하는 최소 전화기 개수를 출력한다.</p> <p>두 번째 줄에 착신 전환 상태를 바꾼 이후 각 전화기의 착신 전환 상태를 의미하는 $N$개의 정수 $b_1, \cdots, b_N$을 출력한다. 만약 가능한 착신 전환 상태가 여러 가지라면, 그중 아무거나 출력한다.</p> ## 풀이 다른 전화기와 착신되지 않은 전화기만 다른 아무 전화기와 연결하면 됩니다. ``` c++ #include<bits/stdc++.h> using namespace std; const int MAX = 100'001; int res[MAX]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i=1;i<=n;i++) cin >> res[i]; int cnt=0; for(int i=1;i<=n;i++) { if(res[i]==i) { res[i] = i%n+1; cnt++; } } cout << cnt << '\n'; for(int i=1;i<=n;i++) cout << res[i] << ' '; } ```