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;
}

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++;
    }
}

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;
}

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++;
    }
}

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;
}

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++;
    }
}

2.最短路

最短路总结：

编辑

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;
}

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];
    }
}

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;
}

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++;
    }
}

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;
}

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);
            }
        }
    }
}

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;
}

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++;
    }
}

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;
}

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++;
    }
}

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;
}

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]);
                }
            }
        }
    }
}

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;
}

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;
    }
}

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;
}

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];
    }
}

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;
}

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++;
    }
}

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;
}

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;
    }
}

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;
}

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];
    }
}

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;
}

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];
    }
}

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;
    }
};

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];
    }
}

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;
    }
};

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];
    }
}

图论算法基础模板

1.树与图的遍历

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

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

1.3.拓扑排序

2.最短路

2.1 Dijkstra

2.1.1 朴素Dijkstra(稠密图)

2.1.2 堆优化Dijkstra(稀疏图)

2.2 bellman-ford

2.2.1 有边数限制的最短路

2.3 spfa

2.3.1 spfa求最短路

2.3.2 spfa判断负环

2.4 Floyd

2.4.1 模板

3.最小生成树

3.1 Prim

3.2 Kruskal

4. 二分图

4.1 染色法判定二分图

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

5.并查集

5.1 合并集合

5.2 连通块中点的数量

5.3 情侣牵手

5.4 相似字符串

热门文章

最新文章

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

图论算法基础模板

1.树与图的遍历

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

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

1.3.拓扑排序

2.最短路

2.1 Dijkstra

2.1.1 朴素Dijkstra(稠密图)

2.1.2 堆优化Dijkstra(稀疏图)

2.2 bellman-ford

2.2.1 有边数限制的最短路

2.3 spfa

2.3.1 spfa求最短路

2.3.2 spfa判断负环

2.4 Floyd

2.4.1 模板

3.最小生成树

3.1 Prim

3.2 Kruskal

4. 二分图

4.1 染色法判定二分图

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

5.并查集

5.1 合并集合

5.2 连通块中点的数量

5.3 情侣牵手

5.4 相似字符串

热门文章

最新文章

相关电子书