Exchange bottles (graph theory + thinking)

sample input 1：

5
3 1 2 5 4

sample output 1：

3

sample input 2：

5
5 4 3 2 1

sample output 2：

2

The idea of this topic is difficult to think about , It is a problem combined with graph theory , We put this n A position can be regarded as n A little bit , For the first i The value of a point a[i], Jean di i Point to point a[i] A dot with a directed edge represents the i The final position of the value at point is a[i] A little bit , Because each point will only have a final position and the position will only be the final position of a point , So after connecting the edges according to the above method, there will only be one out edge and one in edge for each point , That is, it will form several rings , Follow the example first 1 Draw edges and analyze ：

This is the graph built according to the above method , Now let's take a look at what changes will happen when we build a map after exchanging two points

At this time, the discussion should be divided into two situations , One is to exchange two points in a ring , The other is that the two points exchanged are located in two rings

Case one ：（ The two points of exchange are located in a ring , such as 1,2 Point on position ）

be 1 The point on the position will point to 2 The point pointed by the position point , That is to say 1, and 2 The position will point to 1 The point the position points to , That is to say 3, So we'll find out 1 Forming a self ring , So the number of rings decreases 1

The second case ：（ The two points of exchange are located on two different rings , such as 1,5 Point on position ）

be 1 The point on the position will point to 5 The point pointed by the position point , That is to say 4, and 5 The position will point to 1 The point the position points to , That is to say 3, In this way, we will find that the ring of these two points becomes a big ring , That is, the number of rings is reduced 1

Through the analysis of these two situations , We will find that if two points of the exchange are in a ring , Then the number of rings decreases 1, If two points of the exchange are on two different rings , Then the number of rings decreases 1, And our final situation is that all points form a self ring , That is, the number of rings is n, So we should exchange two points in a ring at a time to increase the number of rings 1. So the answer is n- At first, the number of rings

How to calculate the number of rings , A clever method is used here , Refer to code for details ：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=10003;
int a[N]; 
bool vis[N];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			cnt++;
			int t=i;
			while(!vis[t])
			{
				vis[t]=true;
				t=a[t];
			}
		}
	}
	printf("%d",n-cnt);
	return 0;
}