图论算法基础模板

简介: 本文总结了图论和并查集的常见算法实现,包括树与图的遍历(DFS/BFS)、最短路径算法(Dijkstra、Bellman-Ford、SPFA、Floyd)、最小生成树(Prim、Kruskal)、二分图判定与匹配(匈牙利算法)以及并查集的应用。每种算法均提供C++和Java两种实现,涵盖图的存储方式、核心算法逻辑和典型应用场景。这些算法是解决图论问题的基本工具,适用于网络分析、路径规划、连通性判断等多种实际问题。

 1.树与图的遍历

1.1 树与图的深度优先遍历-树的重心

https://www.acwing.com/problem/content/848/

代码实现(C++/Java)

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=N*2;
int n;
int h[N],e[M],ne[M],idx;
int res=N;
bool status[N];
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int dfs(int u){
    status[u]=true;
    int size=0,sum=0;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(!status[j]){
            int s=dfs(j);
            size=max(size,s);
            sum+=s;
        }
    }
    size=max(size,n-sum-1);
    res=min(res,size);
    return sum+1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    memset(h,-1,sizeof(h));
    cin>>n;
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    dfs(1);
    cout<<res<<endl;
    
    return 0;
}

image.gif

import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static int n;
    public static int[]h;
    public static int[]e;
    public static int[]ne;
    public static int idx;
    public static boolean[]status;
    public static int result=0x3f3f3f3f;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        h=new int[n+10];
        e=new int[2*n+10];
        ne=new int[2*n+10];
        status=new boolean[n+10];
        Arrays.fill(h,-1);
        for (int i = 0; i < n - 1; i++) {
            int a=sc.nextInt();
            int b=sc.nextInt();
            add(a,b);
            add(b,a);
        }
        dfs(1);
        System.out.println(result);
    }
    
    //以x为根节点的子节点个数
    public static int dfs(int x){
        status[x]=true;
        int sum=1;//存储以u为根节点的树的节点个数
        int res=0; //删除某个节点后,最大联通子图的节点个数
        for(int i=h[x];i!=-1;i=ne[i]){
            int j=e[i];
            if(!status[j]){
                int s=dfs(j);
                sum+=s;
                res=Math.max(res,s);
            }
        }
        res=Math.max(res,n-sum);
        result=Math.min(result,res);
        return sum;
    }
    public static void add(int a,int b){
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
    }
}

image.gif

1.2 树与图的广度优先遍历-图中点的层次

https://www.acwing.com/problem/content/849/

代码实现(C++/Java)

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int h[N],e[N],ne[N];
int dist[N];
int idx;
int n,m;
void add(int a,int b){
  e[idx]=b;
  ne[idx]=h[a];
  h[a]=idx++;
}
int bfs(){
  memset(dist,-1,sizeof(dist));
  dist[1]=0;
  queue<int> q;
  q.push(1);
  while(q.size()){
    auto t=q.front();
    q.pop();
    for(int i=h[t];i!=-1;i=ne[i]){
      int j=e[i];
      if(dist[j]==-1){
        dist[j]=dist[t]+1;
        q.push(j);
      }
    }
  }
  return dist[n];
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  memset(h,-1,sizeof(h));
  cin>>n>>m;
  for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;
    add(a,b); 
  }
  int res=bfs();
  cout<<res<<endl;
  
  return 0;
}

image.gif

import java.util.*;
public class Main{
    public static final int N= (int) (1e5+10);
    public static int n,m,idx;
    public static int[]h=new int[N];
    public static int[]e=new int[N];
    public static int[]ne=new int[N];
    public static int[] dist=new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Arrays.fill(h,-1);
        n=sc.nextInt();
        m=sc.nextInt();
        for(int i=0;i<m;i++){
            int a=sc.nextInt();
            int b=sc.nextInt();
            add(a,b);
        }
        int res=bfs();
        System.out.println(res);
    }
    private static int bfs() {
        Arrays.fill(dist,-1);
        dist[1]=0;
        Queue<Integer> q=new LinkedList<>();
        q.offer(1);
        while(!q.isEmpty()){
            int t=q.poll();
            for(int i=h[t];i!=-1;i=ne[i]){
                int j=e[i];
                if(dist[j]==-1){
                    dist[j]=dist[t]+1;
                    q.offer(j);
                }
            }
        }
        return dist[n];
    }
    public static void add(int a,int b){
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
    }
}

image.gif

1.3.拓扑排序

https://www.acwing.com/problem/content/850/

代码实现(C++/Java)

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int h[N],e[N],ne[N],idx;
int res[N];
int d[N];//入度
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
bool fun(){
    queue<int> q;
    int cnt=0;
    //入度为0的节点入队
    for(int i=1;i<=n;i++){
        if(d[i]==0) q.push(i);
    }
    while(q.size()){
        int t=q.front();
        q.pop();
        res[cnt++]=t;
        //遍历临边
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            d[j]--;
            if(d[j]==0){
                q.push(j);
            }
        }
    }
    return cnt==n;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    memset(h,-1,sizeof(h));
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
        d[b]++;
    }
    if(!fun()){
        cout<<-1<<endl;
    }else{
        for(int i=0;i<n;i++){
            cout<<res[i]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

image.gif

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
    public static int n,m;
    public static int[]h;
    public static int[]e;
    public static int[]ne;
    public static int[]d;
    public static int idx;
    public static int[]result;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        h=new int[n+10];
        e=new int[2*m+10];
        ne=new int[2*m+10];
        d=new int[n+10];
        Arrays.fill(h,-1);
        for (int i = 0; i < m; i++) {
            int a=sc.nextInt();
            int b=sc.nextInt();
            add(a,b);
            d[b]++; //增加b的入度
        }
        if(!topSort()){
            System.out.println(-1);
        } else{
            for(int i=0;i<n;i++){
                System.out.print(result[i]+" ");
            }
            System.out.println();
        }
    }
    //拓扑排序
    public static boolean topSort(){
        Queue<Integer> q=new LinkedList<>();
        result=new int[n+10];
        int count=0; //加入结果集的节点数
        //入度为0的节点入队
        for(int i=1;i<=n;i++){
            if(d[i]==0){
                q.offer(i);
            }
        }
        while (!q.isEmpty()){
            int t=q.poll();
            result[count++]=t; //将节点加入结果集
            for(int i=h[t];i!=-1;i=ne[i]){
                int j=e[i];
                d[j]--;//删边
                if(d[j]==0){
                    q.offer(j);
                }
            }
        }
        return count==n;
    }
    public static void add(int a,int b){
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
    }
}

image.gif

2.最短路

最短路总结:

image.gif 编辑

2.1 Dijkstra

2.1.1 朴素Dijkstra(稠密图)

https://www.acwing.com/problem/content/851/

代码实现(C++/Java)

#include<bits/stdc++.h>
using namespace std;
const int N=510;
const int MAX=0x3f3f3f3f;
int n,m;
int graph[N][N];
bool status[N];
int dist[N]; 
int djs(){
  for(int i=1;i<=n-1;i++){
    int t=-1;
    for(int j=1;j<=n;j++){
      if(!status[j] && (t==-1 || dist[j]<dist[t])){
        t=j;
      }
    }
    status[t]=true;
    for(int j=1;j<=n;j++){
      if(graph[t][j]!=MAX){
        dist[j]=min(dist[j],graph[t][j]+dist[t]); 
      }
    }
  }
  if(dist[n]==MAX) return -1;
  else return dist[n];
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n>>m;
  memset(dist,MAX,sizeof(dist));
  dist[1]=0;
  memset(graph,MAX,sizeof(graph));
  for(int i=0;i<m;i++){
    int x,y,z;
    cin>>x>>y>>z;
    graph[x][y]=min(graph[x][y],z);
  }
  int res=djs();
  cout<<res<<endl;
  
  return 0;
}

image.gif

import java.util.*;
public class Main {
    public static final int N=510;
    public static final int MAX=0x3f3f3f3f;
    public static int n,m;
    public static int[][]graph;
    public static boolean[]status;
    public static int[]dist;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        graph=new int[N][N];
        status=new boolean[N];
        dist=new int[N];
        n=sc.nextInt();
        m=sc.nextInt();
        Arrays.fill(dist,MAX);
        dist[1]=0;
        for(int i=0;i<N;i++){
            Arrays.fill(graph[i],MAX);
        }
        for(int i=1;i<=m;i++){
            int x=sc.nextInt();
            int y=sc.nextInt();
            int z=sc.nextInt();
            graph[x][y]=Math.min(graph[x][y],z);
        }
        int res=djs();
        System.out.println(res);
    }
    public static int djs(){
        for(int i=1;i<=n-1;i++){
            int t=-1;
            for(int j=1;j<=n;j++){
                if(!status[j] && (t==-1 || dist[j]<dist[t])){
                    t=j;
                }
            }
            status[t]=true;
            for(int j=1;j<=n;j++){
                if(graph[t][j]!=MAX){
                    dist[j]=Math.min(dist[j],dist[t]+graph[t][j]);
                }
            }
        }
        if(dist[n]==MAX) return -1;
        else return dist[n];
    }
}

image.gif

2.1.2 堆优化Dijkstra(稀疏图)

https://www.acwing.com/problem/content/852/

代码实现(C++/Java)

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int MAX=0x3f3f3f3f;
typedef pair<int,int> PII;
int n,m;
int h[N];
int w[N];
int e[N];
int ne[N];
int idx;
int dist[N];
bool status[N];
void add(int a,int b,int c){
  e[idx]=b;
  w[idx]=c;
  ne[idx]=h[a];
  h[a]=idx++;
}
int djstr(){
  priority_queue<PII,vector<PII>,greater<PII>> heap;
  heap.push({0,1});//距离,编号
  while(heap.size()){
    auto t=heap.top();
    heap.pop();
    int distance=t.first;
    int code=t.second;
    if(status[code]) continue;
    status[code]=true;
    //临近节点 
    for(int i=h[code];i!=-1;i=ne[i]){
      int j=e[i];
      if(dist[j]>dist[code]+w[i]){
        dist[j]=dist[code]+w[i];
        heap.push({dist[j],j});
      }
    }
  }
  if(dist[n]==MAX) return -1;
  else return dist[n]; 
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n>>m;
  memset(dist,MAX,sizeof(dist));
  dist[1]=0;
  memset(h,-1,sizeof(h));
  for(int i=0;i<m;i++){
    int a,b,c;
    cin>>a>>b>>c;
    add(a,b,c);
  } 
  int res=djstr();
  cout<<res<<endl;
  
  return 0;
}

image.gif

import java.util.*;
public class Main {
    public static final int N= (int) (1e6+10);
    public static final int MAX=0x3f3f3f3f;
    public static boolean[]status=new boolean[N];
    public static int[]dist=new int[N];
    public static int[] h=new int[N];
    public static int[] e=new int[N];
    public static int[] ne=new int[N];
    public static int[] w=new int[N];
    public static int idx;
    public static int n,m;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        Arrays.fill(dist,MAX);
        dist[1]=0;
        Arrays.fill(h,-1);
        for(int i=0;i<m;i++){
            int a=sc.nextInt();
            int b=sc.nextInt();
            int c=sc.nextInt();
            add(a,b,c);
        }
        int res=dijst();
        System.out.println(res);
        
    }
    private static int dijst() {
        //距离-编号,按距离升序排序
        PriorityQueue<int[]> heap=new PriorityQueue<>((a,b)->a[0]-b[0]);
        heap.offer(new int[]{0,1});
        while(!heap.isEmpty()){
            int[]t=heap.poll();
            int code=t[1];
            int distance=t[0];
            if(status[code]) continue;
            status[code]=true;
            //遍历相邻节点
            for(int i=h[code];i!=-1;i=ne[i]){
                int j=e[i];
                if(dist[j]>dist[code]+w[i]){
                    dist[j]=dist[code]+w[i];
                    heap.offer(new int[]{dist[j],j});
                }
            }
        }
        if(dist[n]==MAX) return -1;
        else return dist[n];
    }
    private static void add(int a, int b, int c) {
        e[idx]=b;
        w[idx]=c;
        ne[idx]=h[a];
        h[a]=idx++;
    }
}

image.gif

2.2 bellman-ford

2.2.1  有边数限制的最短路

https://www.acwing.com/problem/content/855/

代码实现(C++/Java)

#include<bits/stdc++.h>
using namespace std;
const int MAX=0x3f3f3f3f;
const int N=510;
const int M=10010;
struct Edge{
  int a,b,w;
}edges[M];
int n,m,k;
int dist[N];
int last[N];
void bf(){
  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),cout.tie(0);
    cin>>n>>m>>k;
    for(int i=0;i<m;i++){
      int a,b,w;
      cin>>a>>b>>w;
      edges[i]={a,b,w};
  }
  memset(dist,MAX,sizeof(dist));
  dist[1]=0;
  bf();
  if(dist[n]>=MAX/2) cout<<"impossible"<<endl;
  else cout<<dist[n]<<endl; 
      
    return 0;
}

image.gif

import java.util.*;
class Edge{
    int a,b,w;
    public Edge(int a,int b,int w){
        this.a=a;
        this.b=b;
        this.w=w;
    }
}
public class Main {
    public static final int MAX=0x3f3f3f3f;
    public static final int N=510;
    public static final int M=10010;
    public static int n,m,k;
    public static int[]dist=new int[N];
    public static int[]last=new int[N];
    public static Edge[]edges=new Edge[M];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        k=sc.nextInt();
        for(int i=0;i<m;i++){
            int a=sc.nextInt();
            int b=sc.nextInt();
            int w=sc.nextInt();
            edges[i]=new Edge(a,b,w);
        }
        Arrays.fill(dist,MAX);
        dist[1]=0;
        bf();
        if(dist[n]>=MAX/2) System.out.println("impossible");
        else System.out.println(dist[n]);
    }
    private static void bf() {
        for(int i=0;i<k;i++){
            System.arraycopy(dist,0,last,0,dist.length);
            for(int j=0;j<m;j++){
                Edge edge=edges[j];
                dist[edge.b]=Math.min(dist[edge.b],last[edge.a]+edge.w);
            }
        }
    }
}

image.gif

2.3 spfa

2.3.1 spfa求最短路

https://www.acwing.com/problem/content/853/

代码实现(C++/Java)

#include<bits/stdc++.h>
using namespace std;
const int MAX=0x3f3f3f3f;
const int N=100010;
int n,m;
int h[N],e[N],ne[N],w[N];
int idx;
int dist[N];
bool status[N];
void add(int a,int b,int c){
  e[idx]=b;
  w[idx]=c;
  ne[idx]=h[a];
  h[a]=idx++;
}
int spfa(){
  queue<int> q;
  q.push(1);
  status[1]=true;
  while(q.size()){
    int t=q.front();
    q.pop();
    status[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];
        if(!status[j]){
          q.push(j);
          status[j]=true;
        }
      }
    }
  }
  return dist[n];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    memset(h,-1,sizeof(h));
    memset(dist,MAX,sizeof(dist));
    dist[1]=0;
    for(int i=0;i<m;i++){
      int a,b,c;
    cin>>a>>b>>c;
    add(a,b,c); 
  }
    int res=spfa();
    if(res==MAX) cout<<"impossible"<<endl;
    else cout<<res<<endl;
    return 0;
}

image.gif

import java.util.*;
public class Main {
    public static final int MAX=0x3f3f3f3f;
    public static final int N=100010;
    public static int[] h=new int[N];
    public static int[] e=new int[N];
    public static int[] ne=new int[N];
    public static int[] w=new int[N];
    public static int[]dist=new int[N];
    public static boolean[]status=new boolean[N];
    public static int n,m;
    public static int idx;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        Arrays.fill(h,-1);
        Arrays.fill(dist,MAX);
        dist[1]=0;
        for(int i=0;i<m;i++){
            int a=sc.nextInt();
            int b=sc.nextInt();
            int c=sc.nextInt();
            add(a,b,c);
        }
        int res=spfa();
        if(res==MAX) System.out.println("impossible");
        else System.out.println(res);
    }
    public static int spfa(){
        Queue<Integer> q=new LinkedList<>();
        q.offer(1);
        status[1]=true;
        while (!q.isEmpty()){
            int t=q.poll();
            status[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];
                    if(!status[j]){
                        q.offer(j);
                        status[j]=true;
                    }
                }
            }
        }
        return dist[n];
    }
    public static void add(int a,int b,int c){
        e[idx]=b;
        w[idx]=c;
        ne[idx]=h[a];
        h[a]=idx++;
    }
}

image.gif

2.3.2 spfa判断负环

https://www.acwing.com/problem/content/854/                                                                

代码实现(C++/Java)

#include<bits/stdc++.h>
using namespace std;
const int MAX=0x3f3f3f3f;
const int N=100010;
int n,m;
int h[N],e[N],ne[N],w[N];
int idx;
int dist[N];
int cnt[N]; 
bool status[N];
void add(int a,int b,int c){
  e[idx]=b;
  w[idx]=c;
  ne[idx]=h[a];
  h[a]=idx++;
}
int spfa(){
  queue<int> q;
  //负环可能存在任意一点 
  for(int i=1;i<=n;i++){
    q.push(i);
    status[i]=true;
  }
  
  while(q.size()){
    int t=q.front();
    q.pop();
    status[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(!status[j]){
          q.push(j);
          status[j]=true;
        }
      }
    }
  }
  return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    memset(h,-1,sizeof(h));
    memset(dist,0x3f,sizeof(dist));
    dist[1]=0;
    for(int i=0;i<m;i++){
      int a,b,c;
    cin>>a>>b>>c;
    add(a,b,c); 
  }
    if(spfa()) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

image.gif

import java.util.*;
public class Main {
    public static final int MAX=0x3f3f3f3f;
    public static final int N=100010;
    public static int[] h=new int[N];
    public static int[] e=new int[N];
    public static int[] ne=new int[N];
    public static int[] w=new int[N];
    public static int[]dist=new int[N];
    public static int[]cnt=new int[N];
    public static boolean[]status=new boolean[N];
    public static int n,m;
    public static int idx;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        Arrays.fill(h,-1);
        Arrays.fill(dist,MAX);
        dist[1]=0;
        for(int i=0;i<m;i++){
            int a=sc.nextInt();
            int b=sc.nextInt();
            int c=sc.nextInt();
            add(a,b,c);
        }
        if(spfa()) System.out.println("Yes");
        else System.out.println("No");
    }
    public static boolean spfa(){
        Queue<Integer> q=new LinkedList<>();
        for(int i=1;i<=n;i++){
            status[i]=true;
            q.offer(i);
        }
        while (!q.isEmpty()){
            int t=q.poll();
            status[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(!status[j]){
                        q.offer(j);
                        status[j]=true;
                    }
                }
            }
        }
        return false;
    }
    public static void add(int a,int b,int c){
        e[idx]=b;
        w[idx]=c;
        ne[idx]=h[a];
        h[a]=idx++;
    }
}

image.gif

2.4 Floyd

2.4.1 模板

https://www.acwing.com/problem/content/856/

代码实现(C++/Java)

#include<bits/stdc++.h>
using namespace std;
const int MAX=0x3f3f3f3f;
const int N=220;
int dist[N][N];
int n,m,k;
void flyod(){
  for(int a=1;a<=n;a++){
    for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
        dist[i][j]=min(dist[i][j],dist[i][a]+dist[a][j]);
      }
    }
  }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.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]=MAX;
    }
  }
  for(int i=0;i<m;i++){
    int x,y,z;
    cin>>x>>y>>z;
    dist[x][y]=min(dist[x][y],z);
  } 
  flyod();
  for(int i=0;i<k;i++){
    int x,y;
    cin>>x>>y;
    if(dist[x][y]>=MAX/2){
      cout<<"impossible"<<endl;
    }else {
      cout<<dist[x][y]<<endl;
    }
  } 
    
    return 0;
}

image.gif

import java.util.*;
public class Main {
    public static final int MAX=0x3f3f3f3f;
    public static final int N=220;
    public static int n,m,k;
    public static int[][] dist=new int[N][N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        k=sc.nextInt();
        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]=MAX;
            }
        }
        for (int i = 0; i < m; i++) {
            int x=sc.nextInt();
            int y=sc.nextInt();
            int z=sc.nextInt();
            dist[x][y]=Math.min(dist[x][y],z);
        }
        flyod();
        for (int i = 0; i < k; i++) {
            int x=sc.nextInt();
            int y=sc.nextInt();
            if(dist[x][y]>=MAX/2) System.out.println("impossible");
            else System.out.println(dist[x][y]);
        }
    }
    private static void flyod() {
        for(int a=1;a<=n;a++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    dist[i][j]=Math.min(dist[i][j],dist[i][a]+dist[a][j]);
                }
            }
        }
    }
}

image.gif

3.最小生成树

3.1 Prim

https://www.acwing.com/problem/content/860/

代码实现(C++/Java)

#include<bits/stdc++.h>
using namespace std;
const int N=510;
const int MAX=0x3f3f3f3f;
int n,m;
int graph[N][N];
int dist[N];
bool status[N];
int prim(){
  int res=0;
  for(int i=1;i<=n;i++){
    int t=-1;
    for(int j=1;j<=n;j++){
      if(!status[j] && (t==-1||dist[j]<dist[t])){
        t=j;
      }
    }
    status[t]=true;
    if(i>1 && dist[t]==MAX) return MAX;
    if(i>1) res+=dist[t];
    
    for(int j=1;j<=n;j++){
      dist[j]=min(dist[j],graph[t][j]);
    }
  }
  return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
  cin>>n>>m;
  memset(graph,MAX,sizeof(graph));
  for(int i=0;i<m;i++){
    int a,b,c;
    cin>>a>>b>>c;
    graph[a][b]=graph[b][a]=min(graph[a][b],c);
  }
  memset(dist,MAX,sizeof(dist));
  int res=prim();
  if(res==MAX) cout<<"impossible"<<endl;
  else cout<<res<<endl;
    
    return 0;
}

image.gif

import java.util.*;
public class Main {
    public static final int MAX=0x3f3f3f3f;
    public static final int N=510;
    public static int[][] graph=new int[N][N];
    public static int[] dist=new int[N];
    public static boolean[] status=new boolean[N];
    public static int n,m;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        for(int i=0;i<N;i++){
            Arrays.fill(graph[i],MAX);
        }
        for(int i=0;i<m;i++){
            int a=sc.nextInt();
            int b=sc.nextInt();
            int c=sc.nextInt();
            graph[a][b]=graph[b][a]=Math.min(graph[a][b],c);
        }
        Arrays.fill(dist,MAX);
        int res=prim();
        if(res==MAX) System.out.println("impossible");
        else System.out.println(res);
    }
    private static int prim() {
        int res=0;
        for(int i=1;i<=n;i++){
            int t=-1;
            for(int j=1;j<=n;j++){
                if(!status[j] && (t==-1 || dist[j]<dist[t])){
                    t=j;
                }
            }
            status[t]=true;
            if(i>1 && dist[t]==MAX) return MAX;
            if(i>1) res+=dist[t];
            for(int j=1;j<=n;j++){
                dist[j]=Math.min(dist[j],graph[t][j]);
            }
        }
        return res;
    }
}

image.gif

3.2 Kruskal

https://www.acwing.com/problem/content/861/

代码实现(C++/Java)

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int M=2e5+10;
const int MAX=0x3f3f3f3f;
int n,m;
int p[N];
struct Edge{
  int a,b,w;
}edges[M];
int find(int x){
  if(x!=p[x]){
    p[x]=find(p[x]);
  }
  return p[x];
}
int krus(){
  sort(edges,edges+m,[](const Edge e1,const Edge e2){
    return e1.w<e2.w;
  });
  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;
    int b=edges[i].b;
    int w=edges[i].w;
    a=find(a),b=find(b);
    if(a!=b){
      p[a]=b;
      res+=w;
      cnt++; 
    }
  }
  if(cnt<n-1) return MAX;
  return res;
} 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
  cin>>n>>m;
  for(int i=0;i<m;i++){
    int a,b,w;
    cin>>a>>b>>w;
    edges[i]={a,b,w}; 
  }
  int res=krus();
  if(res==MAX) cout<<"impossible"<<endl;
  else cout<<res<<endl;
    
    return 0;
}

image.gif

import java.util.*;
class Edge{
    int a,b,w;
    public Edge(int a,int b,int w){
        this.a=a;
        this.b=b;
        this.w=w;
    }
}
public class Main {
    public static final int N= (int) (1e5+10);
    public static final int M= (int) (2e5+10);
    public static final int MAX=0x3f3f3f3f;
    public static int[] p=new int[N];
    public static Edge[] edges=new Edge[M];
    public static int n,m;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        for(int i=0;i<m;i++){
            int a=sc.nextInt();
            int b=sc.nextInt();
            int w=sc.nextInt();
            edges[i]=new Edge(a,b,w);
        }
        int res=krus();
        if(res==MAX) System.out.println("impossible");
        else System.out.println(res);
    }
    private static int krus() {
        //【0,m】
        Arrays.sort(edges,0,m, new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return Integer.compare(o1.w,o2.w);
            }
        });
        for(int i=1;i<=n;i++){
            p[i]=i;
        }
        int res=0;
        int cnt=0;
        for(int i=0;i<m;i++){
            int a=edges[i].a;
            int b=edges[i].b;
            int w=edges[i].w;
            a=find(a);
            b=find(b);
            if(a!=b){
                p[a]=b;
                res+=w;
                cnt++;
            }
        }
        if(cnt<n-1) return MAX;
        return res;
    }
    private static int find(int x){
        if(x!=p[x]) p[x]=find(p[x]);
        return p[x];
    }
}

image.gif

4. 二分图

4.1 染色法判定二分图

https://www.acwing.com/problem/content/862/

代码实现(C++/Java)

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int M=2e6+10;
int n,m;
int h[N],e[N],ne[N];
int 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),cout.tie(0);
    cin>>n>>m;
    memset(h,-1,sizeof(h));
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    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;
    
    return 0;
}

image.gif

import java.util.*;
public class Main {
    public static final int N=(int)(1e6+10);
    public static final int M=(int)(2e6+10);
    public static int n,m;
    public static int[]h=new int[N];
    public static int[]e=new int[N];
    public static int[]ne=new int[N];
    public static int idx;
    public static int[]color=new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        Arrays.fill(h,-1);
        for(int i=0;i<m;i++){
            int a=sc.nextInt();
            int b=sc.nextInt();
            add(a,b);
            add(b,a);
        }
        boolean flag=true;
        for(int i=1;i<=n;i++){
            if(color[i]==0){
                if(!dfs(i,1)){
                    flag=false;
                    break;
                }
            }
        }
        if(flag) System.out.println("Yes");
        else System.out.println("No");
    }
    private static boolean 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]==0){
                if(!dfs(j,3-c)) return false;
            } else if(color[j]==c){
                return false;
            }
        }
        return true;
    }
    public static void add(int a,int b){
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
    }
}

image.gif

4.2 二分图的最大匹配-匈牙利算法

https://www.acwing.com/problem/content/863/

代码实现(C++/Java)

#include<bits/stdc++.h>
using namespace std;
const int N=510;
const int M=1e6+10;
int n1,n2,m;
int h[N],e[M],ne[M];
int idx;
int match[N];//右侧匹配的左侧
bool status[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(!status[j]){
            status[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),cout.tie(0);
    memset(h,-1,sizeof(h));
    cin>>n1>>n2>>m;
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    int res=0;
    for(int i=1;i<=n1;i++){
        memset(status,false,sizeof(status));
        if(find(i)) res++;
    }
    cout<<res<<endl;
    
    return 0;
}

image.gif

import java.util.*;
public class Main {
    public static final int N=510;
    public static final int M= (int) (1e6+10);
    public static int[]h=new int[N];
    public static int[]e=new int[M];
    public static int[]ne=new int[M];
    public static int idx;
    public static int n1,n2,m;
    public static int[] match=new int[N];
    public static boolean[] status=new boolean[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Arrays.fill(h,-1);
        n1=sc.nextInt();
        n2=sc.nextInt();
        m=sc.nextInt();
        for(int i=0;i<m;i++){
            int u=sc.nextInt();
            int v=sc.nextInt();
            add(u,v);
        }
        int res=0;
        for(int i=1;i<=n1;i++){
            Arrays.fill(status,false);
            if(find(i)) res++;
        }
        System.out.println(res);
    }
    public static void add(int a,int b){
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
    }
    public static boolean find(int x){
        for(int i=h[x];i!=-1;i=ne[i]){
            int j=e[i];
            if(!status[j]){
                status[j]=true;
                if(match[j]==0 || find(match[j])){
                    match[j]=x;
                    return true;
                }
            }
        }
        return false;
    }
}

image.gif

5.并查集

5.1 合并集合

https://www.acwing.com/problem/content/838/

代码实现(C++/Java)

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int p[N];
int find(int x){
  if(p[x]!=x){
    p[x]=find(p[x]);
  }
  return p[x];
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n>>m;
  for(int i=1;i<=n;i++) p[i]=i;
  for(int i=0;i<m;i++){
    char op;
    int a,b;
    cin>>op>>a>>b;
    if(op=='M'){
      p[find(a)]=find(b);
    }else{
      if(find(a)==find(b)){
        cout<<"Yes"<<endl;
      }else{
        cout<<"No"<<endl;
      }
    } 
  }
  
  return 0;
}

image.gif

import java.util.*;
public class Main {
    public static final int N= (int) (1e5+10);
    public static int n,m;
    public static int[] p=new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        for(int i=1;i<=n;i++) p[i]=i;
        for(int i=0;i<m;i++){
            char op=sc.next().charAt(0);
            int a=sc.nextInt();
            int b=sc.nextInt();
            if(op=='M'){
                p[find(a)]=find(b);
            }else{
                if(find(a)==find(b)){
                    System.out.println("Yes");
                }else{
                    System.out.println("No");
                }
            }
        }
    }
    public static int find(int x){
        if(p[x]!=x){
            p[x]=find(p[x]);
        }
        return p[x];
    }
}

image.gif

5.2 连通块中点的数量

https://www.acwing.com/problem/content/839/

代码实现(C++/Java)

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int p[N]; 
int cnt[N];
int find(int x){
  if(p[x]!=x){
    p[x]=find(p[x]);
  }
  return p[x];
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n>>m;
  for(int i=1;i<=n;i++){
    p[i]=i;
    cnt[i]=1;
  }
  for(int i=1;i<=m;i++){
    string op;
    cin>>op;
    if(op=="C"){
      int a,b;
      cin>>a>>b;
      if(find(a)==find(b)){
        continue;
      }
      cnt[find(b)]+=cnt[find(a)];
      p[find(a)]=find(b);
    }else if(op=="Q1"){
      int a,b;
      cin>>a>>b;
      if(find(a)==find(b)){
        cout<<"Yes"<<endl;
      }else {
        cout<<"No"<<endl;
      }
    }else if(op=="Q2"){
      int a;
      cin>>a;
      cout<<cnt[find(a)]<<endl;
    }
  }
  
  return 0;
}

image.gif

import java.util.*;
public class Main {
    public static final int N= (int) (1e5+10);
    public static int n,m;
    public static int[] p=new int[N];
    public static int[] cnt=new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        for(int i=1;i<=n;i++){
            p[i]=i;
            cnt[i]=1;
        }
        
        for(int i=1;i<=m;i++){
            String op=sc.next();
            if(op.equals("C")){
                int a=sc.nextInt();
                int b=sc.nextInt();
                if(find(a)==find(b)) continue;
                cnt[find(b)]+=cnt[find(a)];
                p[find(a)]=find(b);
            }else if(op.equals("Q1")){
                int a=sc.nextInt();
                int b=sc.nextInt();
                if(find(a)==find(b)){
                    System.out.println("Yes");
                }else{
                    System.out.println("No");
                }
            }else if(op.equals("Q2")){
                int a=sc.nextInt();
                System.out.println(cnt[find(a)]);
            }
        }
    }
    public static int find(int x){
        if(p[x]!=x){
            p[x]=find(p[x]);
        }
        return p[x];
    }
}

image.gif

5.3 情侣牵手

765. 情侣牵手 - 力扣(LeetCode)

代码实现(C++/Java)

class Solution {
public:
    int p[80];
    int find(int x){
        if(p[x]!=x) p[x]=find(p[x]);
        return p[x];
    }
    int minSwapsCouples(vector<int>& row) {
        int n=row.size();
        int m=n/2;
        for(int i=0;i<80;i++) p[i]=i;
        for(int i=0;i<n;i+=2){
            int l=row[i]/2;
            int r=row[i+1]/2;
            p[find(l)]=find(r);
        }
        int cnt=0;
        for(int i=0;i<m;i++){
            if(p[i]==i) cnt++;
        }
        return m-cnt;
    }
};

image.gif

class Solution {
    public static int[] p=new int[80];
    public int minSwapsCouples(int[] row) {
        int n=row.length;
        int m=n/2;
        for(int i=0;i<80;i++) p[i]=i;
        for(int i=0;i<n;i+=2){
            int l=row[i]/2;
            int r=row[i+1]/2;
            p[find(l)]=find(r);
        }
        int cnt=0;
        for(int i=0;i<m;i++){
            if(p[i]==i) cnt++;
        }
        return m-cnt;
    }
    public static int find(int x){
        if(p[x]!=x) p[x]=find(p[x]);
        return p[x];
    }
}

image.gif

5.4 相似字符串

839. 相似字符串组 - 力扣(LeetCode)

代码实现(C++/Java)

class Solution {
static const int N=310;
public:
    int p[N];
    int find(int x){
        if(p[x]!=x) p[x]=find(p[x]);
        return p[x];
    }
    int numSimilarGroups(vector<string>& strs) {
        int n=strs.size();
        int m=strs[0].size();
        for(int i=0;i<N;i++) p[i]=i;
        int cnt=n;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                int diff=0;
                for(int k=0;k<m;k++){
                    if(strs[i][k]!=strs[j][k]) diff++;
                }
                if(diff==0 || diff==2){
                    if(find(i)!=find(j)){
                        p[find(i)]=find(j);
                        cnt--;
                    }
                }
            }
        }
        return cnt;
    }
};

image.gif

class Solution {
    public static int N=310;
    public static int[] p=new int[N];
    public int numSimilarGroups(String[] strs) {
        int n=strs.length;
        int m=strs[0].length();
        for(int i=0;i<N;i++) p[i]=i;
        int cnt=n;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                int diff=0;
                for(int k=0;k<m;k++){
                    if(strs[i].charAt(k)!=strs[j].charAt(k)) diff++;
                }
                if(diff==0 || diff==2){
                    if(find(i)!=find(j)){
                        p[find(i)]=find(j);
                        cnt--;
                    }
                }
            }
        }
        return cnt;
    }
    public static int find(int x){
        if(p[x]!=x) p[x]=find(p[x]);
        return p[x];
    }
}

image.gif


相关文章
|
8月前
|
运维 负载均衡 Java
微服务基础1-微服务拆分与服务调用
文章摘要: 本文详细介绍了微服务架构的概念、优势及实现方式。对比单体架构的局限性,微服务通过拆分功能模块实现高内聚、低耦合,提升系统可用性和开发效率。重点讲解了微服务拆分策略(纵向按功能、横向抽通用)、服务注册与发现机制(基于Nacos),以及远程调用方案(RestTemplate和OpenFeign)。OpenFeign通过动态代理简化RPC调用,支持连接池和日志配置,使远程调用如同本地方法。文章还探讨了微服务拆分时机(初创期验证后或大型项目初期直接采用),为不同规模团队提供架构演进建议。
|
8月前
|
监控 算法
算法学习笔记-贪心算法总结1
本文总结了贪心算法在区间问题和实际应用中的典型解法。区间问题包括最大不相交区间、区间选点、无重叠区间、合并区间、区间分组和区间覆盖等6类问题,核心思路都是通过排序处理并维护关键端点。其他应用场景包括合并果子、排队打水、货仓选址等11个问题,展示了贪心算法如何通过局部最优达到全局最优。每种问题都给出了解题思路和示例代码,为处理贪心类算法题提供了系统性的方法论。
|
存储 人工智能 自然语言处理
DeepSeek R1+Open WebUI实现本地知识库的搭建和局域网访问
本文介绍了使用 DeepSeek R1 和 Open WebUI 搭建本地知识库的详细步骤与注意事项,涵盖核心组件介绍、硬件与软件准备、模型部署、知识库构建及问答功能实现等内容,适用于本地文档存储、向量化与检索增强生成(RAG)场景的应用开发。
4976 0
|
9月前
|
人工智能 安全 搜索推荐
2026年年阿里云部署OpenClaw Skills实战:搞定Clawra AI女友+小红书AI运营自动生成发布图文流程
2026年,OpenClaw(前身为Clawdbot、Moltbot)凭借“能动手干活”的核心优势持续爆火,GitHub星标早已突破10万+,成为AI工具领域的现象级项目。它不再是单纯的对话AI,而是能直接操控应用、自动化执行任务的智能代理——既能接入小红书实现全流程社媒运营,又能通过Clawra技能变身“有生活感”的AI女友,真正实现“一个工具,多重身份”。
2330 3
|
5月前
|
人工智能 小程序 程序员
腾讯云放大招了,白薅 Tokens + 免费部署 AI 应用,爽!
AI 投资人 Agent 项目实战保姆级教程,手把手带你用 AI 编程 + EdgeOne Makers 开发毒舌 AI 投资人 Agent,帮你验证副业想法靠不靠谱,覆盖提示词设计、Agent 开发、部署上线、多轮对话记忆全流程。
501 0
腾讯云放大招了,白薅 Tokens + 免费部署 AI 应用,爽!
|
5月前
|
自然语言处理 JavaScript 网络安全
OpenClaw部署教程复刻
OpenClaw(前身为Clawdbot)是开源、本地优先的AI助理框架,支持7×24小时响应、多任务自动化与跨平台协同。兼容Qwen/GPT/Claude等大模型,可处理文件、日程、邮件及多平台操作,是真正落地的“数字员工”。阿里云提供一键部署方案,10分钟即可完成;本地部署则适合快速验证。
|
5月前
|
人工智能 安全 数据挖掘
前有Codex,后有Kimi Work:职场人正在被重新分层
本文探讨AI如何重塑职场生产力:从程序员专属工具(如Codex)扩展至知识工作者,催生“Agent集群”协作范式。职场人正经历三阶段跃迁——从“问答案”到“借外脑”,再到“指挥多Agent团队”完成端到端交付。核心能力转向任务拆解、智能派发与结果验收,未来竞争力在于做AI的“指挥官”,而非执行者。
318 0
|
6月前
|
SQL 关系型数据库 MySQL
【MySQL】事务核心:ACID特性、隔离级别、脏读/不可重复读/幻读、InnoDB RR隔离级别如何解决幻读
本文系统梳理事务核心知识体系,涵盖ACID本质、隔离级别与三类读异常(脏读、不可重复读、幻读)、InnoDB在RR级别下通过MVCC(快照读)和临键锁(当前读)双机制解决幻读的原理,以及底层日志(undo/redo)与锁机制的关联,澄清常见误区,助力深入理解与工程实践。
|
7月前
|
SQL 算法 关系型数据库
击穿 InnoDB 事务隔离级别:RC 与 RR 的底层实现、锁机制、MVCC 与幻读终极拆解
本文深入剖析InnoDB事务隔离原理,聚焦RC(读已提交)与RR(可重复读)的核心差异:从锁机制(记录锁/间隙锁/临键锁)、MVCC可见性规则(Read View生成时机)到幻读解决方案。结合可复现实例与Java实战,助你彻底理解底层逻辑,规避90%的数据不一致与死锁问题。
612 3
|
8月前
|
机器学习/深度学习 监控 Ubuntu
Linux命令速查
Linux命令速查