AcWing 1224. 交换瓶子 解题思路及代码

先贴个题目：

 以及原题链接：1224. 交换瓶子 - AcWing题库https://www.acwing.com/problem/content/1226/

这题没看讲解前我是不会的（谁让我图论一点没学），看了看y总的讲解，只能说学到了。那这题的思路是什么呢？

我们假设一个数，和它本身应该呆的位置的那个数连一个单项边（应该是叫这个吧，就是一个箭头），然后我们把整个数组处理完就会把一个数组变成若干个环， 不难得出，最后如果要把所有的数都变成有序地化，n个数，就是n个自环。然后我们再讨论如果把两个数会对环产生什么影响，如果两个数分属两个环，那么就相当于把两个环合并成了一个环，如果两个数都属于一个环，那么就相当于把一个环裂成两个环，不难发现每次操作要么使总环数+1要么-1。为了让最后数组有序，即变成n个自环，现在的环数为k，那么就应该操作n-k次。

代码如下：

#include<iostream>
using namespace std;

const int N = 1e4 + 10;

int list[N];
bool sign[N];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i < n + 1;++i)
        cin >> list[i];
    int ans=0;
    while(1)
    {
        bool flag = 0;
        int start;
        for (int i = 1; i < n + 1;++i)
        {
            if(!sign[i])
            {
                flag = 1;
                start = i;
                ans++;
                break;
            }
        }
        if(!flag)
            break;
        int now=start;
        while(!sign[now])
        {
            sign[now] = true;
            now = list[now];
        }
    }
    cout << n - ans;
    return 0;
}

一个sign防止重复遍历，然后把所有节点遍历一遍，算出环数，就能解决这题了。

by————2024.4.6刷题记录