Content
- 最短路：Dijkstra、Bellman-Ford、SPFA、Floyd
- 最小生成树：Prim、Kruskal
- 二分图：染色法、匈牙利算法
- 拓扑排序

1️⃣ 最短路介绍

补充：稠密图和稀疏图的定义较模糊，邻接矩阵所需空间$O(n^2)$，邻接表所需空间$O(m)$，计算时间和空间复杂度，选择一个满足的即可。

单源最短路

求一个点到其他所有点的最短距离

分类：

所有边权都是正数
- 朴素Dijkstra算法：O(n^2) （n点数，m边数）、稠密图；用邻接矩阵
- 堆优化版的Dijkstra算法：O(mlogn)、稀疏图；用邻接表
存在负权边
- Bellman-Ford：O(nm)
- SPFA：一般情况下O(m)，最坏O(nm)，也适合正权边；※但是：能用dijkstra的就别用spfa

多源汇最短路

Floyd算法：O(n^3)

Dijkstra - 正权边

从1号点到其他所有点的最短距离

朴素版 - 稠密图 - 邻接矩阵

初始化距离：$dist[1] = 0, dist[i]= +∞$：1号点到起点的距离是1，其他所有点到起点的距离是+∞
集合S：当前已经确定的最短距离的点
for 迭代n次：
- 找到不在S中的距离最近的点 t
- 把t加入S
- 用t更新其他点的距离$dist[j]=min(dist[j],dist[t]+g[t][j]);$

给定一个 n个点 m条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 1 号点到 n号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

注意：若要求任意点i到任意个点j的最短距离，只需修改dijkstra方法中的起源位置dist[i] = 0，以及返回为dist[j]

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n,m;
int g[N][N];
int dist[N];//dist[i]: 从第一个点到第i个点的最短距离 
bool st[N];//st[i]:标记第i个点是否在S中 
int dijkstra(){
	memset(dist,0x3f,sizeof dist);
	dist[1]=0;
	for(int i=0;i<n;i++){ //迭代n次 
		int t=-1;
		for(int j=1;j<=n;j++){//找 不在S中距离的 到第一个点的距离最短的那个点 
			if(!st[j]&&(t==-1||dist[j]<dist[t]))
				t=j;
		}
		for(int j=1;j<=n;j++){ //用这个点 去更新其他点到第一个点的距离 
			dist[j]=min(dist[j],dist[t]+g[t][j]);
		}
		st[t]=true;
	}
	if(dist[n]==0x3f3f3f3f) return -1;
	return dist[n];
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin>>n>>m;
	memset(g,0x3f,sizeof g);
	while(m--){
		int a,b,c;
		cin>>a>>b>>c;
		g[a][b]=min(g[a][b],c);//处理重边 
	}
	int t=dijkstra();
	cout<<t<<endl;
	return 0;
}

堆优化版 - 稀疏图 - 邻接表

适合稀疏图，邻接表存储图

优化：用 堆来存储距离：$mlogn$

找不在S中距离的到源点的距离最短的那个点 👉找一堆数中的最小数👉堆👉$O(1)$
用这个点去更新其他点到第一个点的距离👉堆中修改一个数👉$O(logn)$；

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=150005,M=150005;
int n,m;
int dist[N];
bool st[N];
int h[N],e[M],ne[M],w[M],idx;
void add(int x,int y,int z){
	e[idx]=y,ne[idx]=h[x],w[idx]=z,h[x]=idx,idx++;
	
}
int dijkstra(){
	memset(dist,0x3f,sizeof dist);
	dist[1]=0;
	priority_queue<PII,vector<PII>,greater<PII>>heap; //小根堆
//	heap维护的是 不在S中的点以及它们离起点的距离 
	heap.push({0,1});//dist=0 point=1；
	while(heap.size()){ 
		PII k=heap.top();   //O(m) * O(1) -> O(m)
		heap.pop();
		int ver=k.second,distance=k.first;
		if(st[ver]) continue;
		st[ver]=true;  //O(m) * O(1) -> O(m)
//	用当前点更新其他点的距离 
		for(int i=h[ver];i!=-1;i=ne[i]){
			int j=e[i];
			if(dist[j]>distance+w[i]){
				dist[j]=distance+w[i];
				heap.push({dist[j],j});  // 堆的插入操作时间复杂度是 O(log(n))
                                         // O(m) * O(log(n)) -> O(mlog(n))
			}
		}
	} 
	if(dist[n]==0x3f3f3f3f) return -1;
	return dist[n];
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	memset(h,-1,sizeof h);
	cin>>n>>m;
	while(m--){
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
	}
	cout<<dijkstra()<<endl;
	return 0;
}

Bellman-Ford - 负权边

思想：

1. 初始化源点到各顶点的路径距离。
    
2. 进行n - 1次遍历，每次遍历对 所有边 进行 “松弛操作”。
   松弛操作：以a为起点，b为终点，ab边长度为w为例：
    	dist[a]代表 源点 到 a点 的路径长度，dist[b]代表源点s到b点的路径长度。
    	if：dist[b] > dist[a] + w	then：dist[b] = dist[a] + w。
    
3. 遍历都结束后，若再进行一次遍历，还能得到s到某些节点更短的路径的话，则说明存在负权回路

参考阅读：Bellman——Ford算法

AcWing 853 有边数限制的最短路 - 结构体

对所有边操作，可以直接采用一个结构体定义每条边

1
2
3

for 迭代n次 //这个n其实就是限制了从源点经过不超过n条边到达某些点
    for 所有m条边a-b：w
        dist[b]=min(dist[b],dist[a]+w);

n 个点 m 条边有向图，可能存在重边和自环， 边权可能为负数。

求从 1 号点到 n 号点的最多经过 k 条边的最短距离

注意：图中可能 存在负权回路 ，则不一定存在最短距离。

#include<bits/stdc++.h>
using namespace std;
const int N=505,M=10010;
struct Edge{
	int a,b,w;
}edges[M]; 
int n,m,k;
int dist[N];
int last[N];

void bellman_ford(){
	memset(dist,0x3f,sizeof dist);
	dist[1]=0; 
	for(int i=0;i<k;i++){
		memcpy(last,dist,sizeof dist);  //
		for(int j=0;j<m;j++){
			auto e = edges[j];
			dist[e.b] = min(dist[e.b],last[e.a]+e.w); 
		}
	}
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n>>m>>k;
	for(int i=0;i<m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		edges[i] ={x,y,z};
	}
	bellman_ford();
	if(dist[n] > 0x3f3f3f3f / 2)  cout<<"impossible"<<endl;
	else cout<<dist[n]<<endl;
}

SPFA - 正/负权

Shortest Path Faster Algorithm

思想：

对Bellman-Ford算法的优化：队列
Bellman_ford算法会遍历所有的边，但其实只有当一个点的前驱结点更新，该点才会更新；所以只需遍历那些到源点距离变小的点所连接的边即可👉创建一个队列存放每一次加入距离被更新（变小）的结点

AcWing 851 spfa求最短路

1≤n,m≤$10^5$,用bellman-ford会TLE

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m;
int h[N],e[N],w[N],ne[N],idx;
int dist[N];
bool st[N];

void add(int a,int b,int c){
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

int spfa(){
	memset(dist,0x3f,sizeof dist);
	dist[1]=0;
	
	queue<int>q;//存放距离变小的边 
	q.push(1);
	st[1]=true; //st：当前点是否在队列中，防止存重复点 
	while(q.size()){
		int t=q.front();
		q.pop();
		st[t]=false;
		for(int i=h[t];i!=-1;i=ne[i]){//t变小了，说明所有t的出边对应的点也会变小 
			int j=e[i];
			if(dist[j]>dist[t]+w[i]){
				dist[j]=dist[t]+w[i];
				if(!st[j]){
					q.push(j);
					st[j]=true;
				}
			}
		}
	}
	return dist[n];
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n>>m;
	memset(h,-1,sizeof h);
	while(m--){
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
	}
	int t=spfa();
	if(t==0x3f3f3f3f) cout<<"impossible"<<endl;
	else cout<<t<<endl;
	return 0;
}

AcWing 852 spfa判断负环

加一个cnt数组，cnt[i]记录到顶点i经过的最短路径条数，大于等于n说明存在负环

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int h[N],e[N],w[N],ne[N],idx;
int n,m;
int dist[N]; //关键是看dist有没有更新，值不重要
bool st[N];
int cnt[N]; 
void add(int a,int b,int c){
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
bool spfa(){
	queue<int>q;
	for(int i=1;i<=n;i++){
		st[i]=true;
		q.push(i);
	}//判断是否存在负环，而不是 是否存在从1开始到达的负环，所以要把所有点加进去，此时dist也不用初始化了
	while(q.size()){
		int t=q.front();
		q.pop();
		st[t]=false;
		for(int i=h[t];i!=-1;i=ne[i]){
			int j=e[i];
			if(dist[j]>dist[t]+w[i]){
				dist[j]=dist[t]+w[i];
				cnt[j]=cnt[t]+1;
				if(cnt[j]>=n) return true;
				if(!st[j]){
					st[j]=true;
					q.push(j);
				}
			}
		}
	}
	return false;
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n>>m;
	memset(h,-1,sizeof h);
	for(int i=0;i<m;i++){
		int a,b,c;cin>>a>>b>>c;
		add(a,b,c);
	}
	if(spfa()) puts("Yes");
	else puts("No");
	return 0;
}

Floyd - 任意两点之间

⭐一个踩坑点⭐：

ios::sync_with_stdio(false) 取消cin的同步（就是iostream的缓冲跟stdio的同步）取消后就cin就不能和scanf，sscanf, getchar, fgets，puts之类同时用，💔否则就可能导致输出和预期的不一样。

刚开始取消同步，用puts输出impossible，发现顺序不对，还以为是代码问题QAQ，后来改成cout就AC了

#include<bits/stdc++.h>
using namespace std;
const int N=210,M=20010,INF=1e9;
int dist[N][N];
int n,m,k;

void floyd(){
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}

int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			if(i==j) dist[i][j]=0;
			else dist[i][j]=INF;
		}
	for(int i=0;i<m;i++){
		int x,y,z; cin>>x>>y>>z;
		dist[x][y]=min(dist[x][y],z);
	}
	floyd();
	while(k--){
		int x,y; cin>>x>>y;
		if(dist[x][y]>INF/2) cout<<"impossible"<<endl;;
		else cout<<dist[x][y]<<endl;
	}
	return 0;
}

💦分层图💦：堆优化Dijkstra+建图

参考阅读：分层图

$n$ 个点 $m$ 条边构成一张带权无向连通图。现在可以从中选出 $k$ 条边，将边权变为零。求给定两点间最短路径。

将点拆开，复制多层图，并利用特殊构造的边将各层相连的建图方法。

一般用于边或点有特殊限制的问题(如重复经过次数、多种价值可选等)。

需要保证拆开后的总点数规模可接受。

空间复杂度及时间复杂度较高，（可以理解为2个点互连的有向图）
- 空间复杂度为$m\times (k+1)$，无向图在此基础上乘2

关键在建图

两种方法解决：
1. 建图时直接建成k+1层。
2. 多开一维记录机会信息。

P4568 飞行路线 - 洛谷

题意： n 个城市，这些城市分别标记为 0 到 n-1，共 m种航线，每种航线连接两城市，航线有一定的价格。从一个城市沿着航线到达另一个城市，途中可进行转机。可免费在最多 k种航线上搭乘飞机。问这次出行最少花费

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;

const int N=1e4+10,M=5e4+10,K=50; //注意这里的数据范围，不然被TLE

int h[N*K],e[M*K<<1],ne[M*K<<1],w[M*K<<1],idx;
int dist[N*K];
bool st[N*K];
int n,m,s,t,k;

// 规定顶点编号从1开始 
// 稀疏图，堆优化dijkstra 
void add(int a,int b,int c){
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dijkstra(){
	memset(dist,0x3f,sizeof dist);
	dist[s]=0;
	priority_queue<PII,vector<PII>,greater<PII>>heap;
	heap.push({0,s});
	while(!heap.empty()){
		PII k=heap.top();
		heap.pop();
		int ver=k.second,distance=k.first;
		if(st[ver]) continue;
		st[ver]=true;
		for(int i=h[ver];i!=-1;i=ne[i]){
			int j=e[i];
			if(dist[j]>distance+w[i]){
				dist[j]=distance+w[i];
				heap.push({dist[j],j});
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n>>m>>k>>s>>t;
	s++;t++;
	memset(h,-1,sizeof h); 
	
	for(int i=0;i<m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		a++;b++;
		add(a,b,c),add(b,a,c);
		//建立分层图
		for(int i=1;i<=k;i++){
			add(n*i+a,n*i+b,c);
			add(n*i+b,n*i+a,c);
			//两层之间建边
			add(n*(i-1)+a,n*i+b,0);
			add(n*(i-1)+b,n*i+a,0); 
		} 
	}
	//for(int i=1;i<=k;i++) add(n*(i-1)+t,n*i+t,0);
	
	dijkstra();
	int ans=0x3f3f3f3f;
	for(int i=0;i<=k;i++) ans=min(ans,dist[t+i*n]);
	cout<<ans<<endl;
	return 0;
}

同类题目：P4822 冻结 - 洛谷

修改一下起止点，两层之间建边的权值改为c/2 即可

2️⃣ 最小生成树

生成树：包含 所有顶点的 极小连通子图
最小生成树：带权连通无向图的 边的权值之和最小的那棵生成树

Prim-稠密图：$O(n^2)$

基于贪心：每次加入距离连通部分（已确定最小生成树的部分）的最近的点和对应边，连通部分逐渐扩大至整个图连通，且边权和最小。

参考阅读题解

针对无向图
先累加再更新，避免t有自环影响答案。
- 后更新不会影响后面的结果：因为dist[i]为i到集合S的距离，当t放入S后，其dist[t]就已经没有意义，再更新也不会影响答案的正确性。
特判一下第一次迭代，在没有做特殊处理时，第一次迭代中所有点到集合S的距离都为无穷大，且不会进行更新(也没有必要)，不需要将这条边 (第一次迭代时，找到的距离集合S最短的边) 累加到答案中，也不能认定为图不连通。
如果设置起点为i的话，在初始化dist数组之后，dist[i] = 0即可，省去每轮迭代中的两个if判断。

AcWing 858 Prim算法求最小生成树

#include<bits/stdc++.h>
using namespace std;
const int N=510,INF=0x3f3f3f3f;
int n,m;
int g[N][N]; //结点 i 到 j 的距离
int dist[N]; //存储各个结点到已确定的生成树（顶点集S）的距离；区分dijkstra：到源点的距离 
bool st[N];  //顶点是否加入到MST

int prim(){
	memset(dist,0x3f,sizeof dist);
	int res = 0;
	for(int i=0;i<n;i++){
		int t=-1;
		// 找剩余点到已确定生成树距离最近的点 
		for(int j=1;j<=n;j++){
			if(!st[j]&&(t==-1||dist[j]<dist[t]))
				t=j;
		}
		if(i&&dist[t]==INF) return INF;//图不连通
		if(i) res+=dist[t];
		st[t]=true;
		
		for(int j=1;j<=n;j++)  //更新剩余点到已确定的生成树的距离 
			dist[j]=min(dist[j],g[t][j]); //区分dijkstra：dist[t]+g[t][j] 
	}
	return res;
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n>>m;
	memset(g,0x3f,sizeof g);
	for(int i=0;i<m;i++){
		int a,b,c;cin>>a>>b>>c;
		g[a][b]= g[b][a]=min(g[a][b],c);
	}
	int t=prim();
	if(t==INF) cout<<"impossible"<<endl;
	else cout<<t<<endl;
	return 0;
}

堆优化Prim-稀疏图

$O(mlogn)$（不常用、略过，一般遇见稀疏图用下面的Kruskal）

Kruskal-稀疏图：$O(mlogm)$

主要对边进行操作，比如对边进行排序，考虑采用 结构体 建图
一条边依附的两个顶点在不同连通分量上：并查集
prim算法需要更新其他点到集合的距离，用到边的权重，需要两条
但在kruskal用并差集维护，枚举的是边不是点，

思想：

初始：n个顶点而无边的非连通图，每个顶点自成一个连通分量
按边的权值从小到大的顺序
不断选取当前未被选过且权值最小的边
- 若该边依附的两顶点落在T中不同的连通分量上，加入T
- 否则，舍弃此边，选择下一条权值最小的边；
直到所有顶点都在一个连通分量上

结构体排序：

结构体内部定义

1
2
3

bool const< (const Edge&W)const{
    return w<W.w
} // sort(edges,edges+m);

cmp外部函数定义

1
2
3

bool cmp(struct Edge A, struct Edge B){
	return A.w < B.w;
} // sort(edges,edges+m,cmp);

Lambda表达式

1	sort(edges ,edges + m,[](auto & u,auto & v){return u.w < v.w ;});

AcWing 859 Kruskal算法求最小生成树

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=2*N,INF=0x3f3f3f3f;
int n,m;
int p[N];
struct Edge{
	int a,b,w;
	bool operator< (const Edge&W)const{
		return w<W.w;
	}
}edges[M];

int find(int x){
	if(p[x]!=x) p[x]=find(p[x]);
	return p[x];
}

int kruskal(){
	sort(edges,edges+m);
	for(int i=1;i<=n;i++) p[i]=i;
	
	int res=0,cnt=0;
	for(int i=0;i<m;i++){
		int a=edges[i].a, b=edges[i].b, w=edges[i].w;
		a=find(a),b=find(b);
		if(a!=b){
			p[a]=b;
			res+=w;
			cnt++;
		}
	}
	if(cnt<n-1) return INF;
	return res;
}

int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int a,b,c;cin>>a>>b>>c;
		edges[i]={a,b,c};
	}
	int t=kruskal();
	if(t==INF) cout<<"impossible"<<endl;
	else cout<<t<<endl;
}

3️⃣ 二分图

参考阅读：图论 —— 二分图

概念：

⭕ 二分图定义：设G=(V,E)是一个无向图，如果顶点集V 可分割为两个互不相交的子集 $(A,B)$，并且图中的每条边$（i，j）$所关联的两个顶点 $i$ 和 $j$ 分别属于这两个不同的顶点集$(i \in A,j \in B)$，则称图G为一个二分图（二部图、偶图）

⭕ 完全二分图：集合A中的所有顶点都与集合B中的所有顶点相连的二分图

⭕ 判定二分图的充要条件：图 G 中至少存在两个点，且图中所有回路的长度均为偶数

AcWing 860 判定二分图：染色法

$O(m+n)$

染色法思想：

开始：对任意一个未染色的顶点染色。
判断其相邻的顶点中，若未染色，则将其染上和相邻顶点不同的颜色。
若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=2*N;
int n,m;
int h[N],e[M],ne[M],idx;
int color[N];
void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool dfs(int u,int c){
	color[u]=c;
	for(int i=h[u];i!=-1;i=ne[i]){
		int j=e[i];
		if(!color[j]){
			if(!dfs(j,3-c)) return false;
		}else{
			if(color[j]==c) return false;
		} 
	}
	return true;
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	memset(h,-1,sizeof h);
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int u,v;cin>>u>>v;
		add(u,v),add(v,u);
	}
	bool flag = true;
	for(int i=1;i<=n;i++){
		if(!color[i]){
			if(!dfs(i,1)){
				flag=false;
				break;
			}
		}
	}
	if(flag) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}

AcWing 861 二分图的最大匹配：匈牙利算法

最坏$O(mn)$，实际运行一般远小于它

二分图的匹配：

⭕ 匹配：在给定一个二分图 G，在 G 的一个子图 M 中，若 M 的边集中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。

匹配：一个二分图中边的集合，其中任意两条边都没有公共顶点

完美匹配：一个图的某个匹配中，所有的顶点都是匹配点

交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。

增广路：从一个未匹配点出发，走交替路，途径另一个未匹配点（出发的点不算）

⭕ 最大匹配：给定二分图 G 中的所有匹配，所含匹配边数最多的匹配

st[ ]数组：可以理解为“预定数组”，比如：看成男女配对，即某一轮中某个女孩是不是被男生预定了。如果find函数递归下去能够帮心仪对象的对象找到备胎，那皆大欢喜；找不到备胎，预定姑娘就保持不动。

#include<bits/stdc++.h>
using namespace std;
const int N=510,M=1e5+10;
int n1,n2,m;
int h[N],e[M],ne[M],idx;
int match[N]; //match[j]=x：右边的j和左边的x配对
bool st[N];   //
void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

bool find(int x){
	for(int i=h[x];i!=-1;i=ne[i]){
		int j=e[i];
		if(!st[j]){
			st[j]=true;
			if(match[j]==0||find(match[j])){
				match[j]=x;return true;
			}
		}
	}
	return false;
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n1>>n2>>m;
	memset(h,-1,sizeof h);
	for(int i=0;i<m;i++){
		int u,v;cin>>u>>v;
		add(u,v);
	}
	int ans=0;
	for(int i=1;i<=n1;i++){
		memset(st,false,sizeof st);
		if(find(i)) ans++;
	}
	cout<<ans<<endl;
	return 0;
}

4️⃣ 拓扑排序

其他

AcWing1224 交换瓶子

题意

N个随机排列的数字，编号1-N，每次交换任意两个数字，直到最后序号为1-N的升序，求最小交换次数

思路

把每个瓶子看成一个点，将每个瓶子向它应该在的位置的编号

代码

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010;
int n;
int b[N];
bool st[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", n - cnt);
    return 0;
}
作者：yxc
链接：https://www.acwing.com/activity/content/code/content/174698/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

另外，暴力出奇迹

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int a[N];
int main(){
	int n,cnt=0;cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		if(a[i]!=i){
			for(int j=i+1;j<=n;j++){
				if(a[j]==i){
					swap(a[i],a[j]);cnt++;
				}
			}
		}
	}
	cout<<cnt<<endl;
}

LiaN

【数据结构】最短路+最小生成树+二分图