目录
并查集
最小生成树（克鲁斯卡尔）
最短路（Dijkstra）
最短路（SPFA）
最短路（Floyd）
拓扑排序
欧拉路径
并查集
int fa[MAX];
void init(){
for(int i=0;i<MAX;i++)fa[i]=i;
}
int find(int i){
int temp=i;
while(temp!=fa[temp])temp=fa[temp];
if(temp!=i){
int t=fa[i];
fa[i]=temp;
i=t;
}
return temp;
}
void merge(int a,int b){
fa[a]=b;
}
最小生成树（克鲁斯卡尔）
struct edge {
int u,v,w;
};
int n,m,a,b,c;
vector<edge> v;
bool cmp(edge a,edge b) {
return a.w<b.w;
}
int kruskal(){
init(); // 初始化并查集
int ans=0;
sort(v.begin(),v.end(),cmp); // 按照边权值的大小排序
for(int i=0; i<v.size(); i++) { // 依次选择权值小的边
int a=find(v[i].u);
int b=find(v[i].v);
if(a!=b) { // 判断这两个点是否已经连接
merge(a,b);
ans+=v[i].w;
}
}
return ans;
}
最短路（Dijkstra）
int vis[MAX],d[MAX];
int w[MAX][MAX];
// 以邻接矩阵存储图
void dijkstra(){
memset(vis,0,sizeof(vis)); // 初始化vis数组
for(int i=1;i<=n;i++)d[i]=w[1][i]; // 初始化到起点的距离
vis[1]=1;
for(int i=1;i<=n;i++){
int minn=INF,k=0;
for(int j=1;j<=n;j++) // 寻找当前路径最短的点
if(!vis[j] && d[j]<minn)
minn=d[j],k=j;
vis[k]=1;
for(int j=1;j<=n;j++) // 松弛操作
if(!vis[j] && minn+w[k][j]<d[j])d[j]=minn+w[k][j];
}
}
最短路（SPFA）
struct node { // 连接的点和到达该点的时间
int to,time;
};
vector<node> G[MAX];
int n,m,a,b,c;
int vis[MAX],d[MAX];
// 以邻接表存储图
void spfa() {
memset(vis,0,sizeof(vis)); // 初始化vis数组
for(int i=0; i<MAX; i++) d[i]=INF; // 初始化距离最大
queue<node> q;
q.push({1,0}); // 起点入列
vis[1]=1; // 进入队列标志
d[1]=0; // 起点距离为0
while(!q.empty()) {
node u=q.front(); q.pop();
vis[u.to]=0; // 出队列标志
for(int i=0; i<G[u.to].size(); i++) { // 遍历所有邻接的点
node v=G[u.to][i];
if(d[v.to]>d[u.to]+v.time) { // 松弛操作
d[v.to]=d[u.to]+v.time;
if(!vis[v.to]) { // 如果没有入列则入列
vis[v.to]=1;
q.push(v);
}
}
}
}
}
最短路（Floyd）
int w[MAX][MAX];
// 以邻接矩阵存储图
void floyd(){
for(int k=1;k<=n;k++){ // 作为中间节点
for(int i=1;i<=n;i++){
if(w[i][k]!=INF){
for(int j=1;j<=n;j++){
w[i][j]=min(w[i][j],w[i][k]+w[k][j]); // 松弛操作
}
}
}
}
}
拓扑排序
int w[MAX][MAX];
int rd[MAX]; // 存储结点的入度
int vis[MAX];
int topo[MAX]; // 拓扑排序后的顺序
// 以邻接矩阵存储图
bool toposort(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(!vis[j]&&rd[j]==0){ // 没有遍历过且入度为0
vis[j]=1;
topo[i]=j;
for(int k=1;k<=n;k++) // 删除以这个点为弧尾的边，并将入度减1
if(w[j][k]){w[j][k]=0;rd[k]--;}
break;
}
}
}
for(int i=1;i<=n;i++) // 如果有节点没有遍历到，说明有环
if(!vis[i])return 0;
return 1;
}
欧拉路径
int g[MAX][MAX]; // 邻接矩阵存储图，元素为结点间边的数量
int d[MAX]; // 存储结点的度
int path[MAX],p=0; // 存储欧拉路径
// 无向图欧拉路径
bool eulor(){
int cnt=0;
for(int i=1;i<=n;i++) // 并查集判断图是否连通
if(fa[i]==i)cnt++;
if(cnt!=1)return 0;
cnt=0;
for(int i=1;i<=n;i++) // 无向图判断是否只有两个度为奇数的结点（欧拉通路）
if(d[i]%2==1)cnt++; // 或者无度为奇数的结点（欧拉回路）
if(cnt==0||cnt==2)return 1;
return 0;
}
// dfs求欧拉路径
void dfs(int start){ // 给予欧拉路径起始点
for(int j=1;j<=n;j++){
if(g[start][j]){
g[start][j]--;g[j][start]--;
dfs(j);
if(g[start][j])j--;
}
}
path[p++]=start; // 存储欧拉路径
}
