AcWing 1224. 交换瓶子 题解 图论思维题

可以把本题抽象一道图论题

把每个瓶子抽象成一个点每个瓶子向它应该在的位置的瓶子结点连一条边因为有n个点，所以可以连n条边这样就构成了一个图，它具有的性质：
1：n个点，n条边
2：每个点的出度、入度都为1这样的图必然是一堆环，一个环我们称为置换

现在我们考虑交换两个点

交换同一个环内的点：原先的环裂成了两个环交换两个不同环中的点：将原先的两个环合并成了一个环

假设初始状态图中有 k k k个环，最终所有的瓶子都放到了应该放的地方，图中会有 n n n个自环
而每次操作最多增加一个环，只要原先的环中结点 ≥ 2 ≥2 ≥2，那么一定存在某种交换操作能把它裂开
所以至少要进行 n − k n-k n−k次交换，就能达到目的效果

#include
using namespace std;
const int N=10010;
int n;
bool st[N];
int b[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    
    int cnt=0;  //记录环的个数
    for(int i=1;i<=n;i++)
        if(!st[i])   
        {
            cnt++;   //找到一个环
            for(int j=i;!st[j];j=b[j]) //遍历环中的所有结点
                st[j]=true;
        }
    printf("%d",n-cnt);
    return 0;
}

表面上看时间复杂度有两重循环，但其实因为有了判重数组st，实际复杂度大大降低了，是 O ( n ) O(n) O(n)的。