題目：

1224. 交換瓶子 - AcWing題庫

輸入樣例1：

5
3 1 2 5 4

輸出樣例1：

3

輸入樣例2：

5
5 4 3 2 1

輸出樣例2：

2

思路：圖論?

1.將對應的位置與當前的瓶子序列相連形成環。

2.最少交換次數=能形成的最多環數n-當前形成的環數cnt

?代碼：

#include<cstdio>
#include<iostream>
using namespace std;
const int N=10010;
int b[N];//儲存輸入的瓶子序列
bool st[N];//判斷相應編號的瓶子是否出現過
int cnt;//表示環的數量
int main()
{int n;cin>>n;for(int i=1;i<=n;i++)scanf("%d",&b[i]);for(int i=1;i<=n;i++){if(!st[i])//該序列瓶子未出現過{cnt++;//環數量+1//將同i在同一個環的瓶子序列全部標記for(int j=i;!st[j];j=b[j])st[j]=true;}}//最少交換次數=n個數最多能形成的環數-當前環數（同環內兩瓶子每交換一次環數+1）cout<<n-cnt;
}