蓝桥杯图论模板

傷城~ 2021-11-13 19:52 380阅读 0赞

### 1.树的直径 ###

#### dfs版 ####

#include<bits/stdc++.h>
    using namespace std;
    
    const int maxn = 1e5+5;
    vector<int> v[maxn];//邻接表 
    int deeper = 0; //1.第一次dfs结果为树的最大深度 2.第二次dfs结果为树的直径
    int node = 1;//初始化为root
    
    void dfs(int x,int dis){
        vis[x] = 1; 
        bool isLeaf = false;
        for(int i=0;i<v[x].size();i++){
            int vv = v[x][i];
            if(!vis[vv]){
                isLeaf = true;
                dfs(vv,dis+1);
            }
        }
        if(!isLeaf){
            if(dis > deeper){
                deeper = dis;
                node = vv;
            }
        }
        vis[x] = 0;
    }
    
    int main()[
        dfs(1,0);
        dfs(node,0);
        return 0;
    }

#### bfs版 ####

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <queue>
    using namespace std;
    
    struct edge{
        int v,w;
        edge(int v,int w){
            this -> v = v;
            this -> w = w;
        }
    };
    vector<edge> vec[10001];
    int d[10001],ans;
    bool vis[10001];
    int node; // 记录第一次dfs最远的点
    void bfs(int u){
        queue<int> q;
        q.push(u);
        while(!q.empty()){
            int x = q.front();
            vis[x] = 1;
            q.pop();
            for(int i = 0;i < (int)vec[x].size();i++){
                int y = vec[x][i].v;
                if(vis[y]) continue;
                d[y] = d[x] + vec[x][i].w;
                if(d[y] > ans){
                    ans = d[y];
                    node = y;
                }
                q.push(y);
            }
        }
    }
    int main(){
        // freopen("test.txt","r",stdin);
        int u,v,w;
        while(scanf("%d%d%d",&u,&v,&w) == 3){
            vec[u].push_back(edge(v,w));
            vec[v].push_back(edge(u,w));
        }
        memset(vis,0,sizeof(vis));
        ans = 0;
        d[1] = 0;
        bfs(1);
        memset(vis,0,sizeof(vis));
        ans = 0;
        d[node] = 0;
        bfs(node);
        printf("%d\n",ans);
        return 0;
    }

### 2.带权并查集 ###

#include<bits/stdc++.h>
    using namespace std;
    
    const int maxn = 1e6+10;
    
    int n,m;//n个顶点 m条边 
    int father[maxn]; //元素父亲节点 
    int size[maxn];//集合大小 
    int maxs[maxn];//集合最大值 
    int dist[maxn];//元素x到它所在集合根节点的距离 
    int setNums = 0;//集合总数 
    
    //初始化 
    void init(){
        setNums = n;
        for(int i=1;i<=n;i++){
            father[i] = i;
            size[i] = 1;
            maxs[i] = i;
            dist[i] = 0;
        }
    }
    
    //查找 
    int find(int x){
        if(father[x] == x){
            return x;
        }
        int y = father[x];
        father[x] = find(y);
        dist[x] += dist[y]; //x到根的距离 需要加上y到根的距离 
        return father[x];
    }
    
    //合并 
    void join(int x,int y){
        int a = find(x);
        int b = find(y);
        if(a != b){
            setNums--;
            father[a] = b;
            dist[a] = size[b];
            size[b] += size[a];
            maxs[b] = max(maxs[a],maxs[b]);
        }
    }
    
    //查询集合总数量 
    int findSetnum(){
        return setNums;
    }
    
    //查询x所在集合的大小(元素数量)
    int findSize(int x){
        return size(find(x));
    }
    
    //查询x所在集合中的最大值 
    int findSetMax(int x){
        return maxs(find(x));
    }
    
    //查询x到它的集合的根 的距离
    int findDist(int x){
        return dist[x];
    }
    
    int main(){
        
        return 0;
    }

### 3.最短路 ###

#### floyd ####

#include<bits/stdc++.h>
    using namespace std;
    
    const int maxn = 1010;
    int g[maxn][maxn];
    const int inf = 0x3f3f3f3f;
    
    void init(){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i==j) g[i][j] = 0;
                else g[i][j] == inf;
            }
        }
    }
    
    void floyd(){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                for(int k=1;k<=n;k++){
                    if(g[i][j] > g[i][k] + g[k][i]){
                        g[i][j] = g[i][k] + g[k][i];
                    }
                }
            }
        }
    }
    
    int main(){
        init();
        floyd();
        return 0;
    }

#### SPFA ####

void spfa(int s){
        memset(inq,0,sizeof(inq));
        memset(d,0x3f3f3f3f,sizeof(d));
        d[s] = 0;
        inq[s] = true;
        queue<int> q;
        q.push(s);
        while(!q.empty()){
            int u = q.front();
            q.pop();
            inq[u] = false;
            for(int i=0;i<v[u].size();i++){
                int vv = v[u][i].x;
                if(d[vv] >  d[u] + v[u][i].w){
                    d[vv] = d[u] + v[u][i].w;
                    if(!inq[vv]){
                        q.push(vv);
                        inq[vv] = 1;
                    }
                }
            }
        }
    }

#### dijkstra ####

bool dijkstra(int s){
        memset(vst,0,sizeof(vst));
        memset(dist,0x3f3f3f3f,sizeof(dist));
        dist[s] = 0;
        for(int i=0;i<n;i++){
            int v,min_w = inf;
            for(int j=0;j<n;j++){
                if(!vst[j] && dist[j] < min_w){
                    min_w = dist[j];
                    v = j;
                }
            }
            if(min_w == inf){ //有顶点无法从原点到达 
                return false;
            }
            vst[v] = true;
            for(int j=p[v];j!=-1;j=e[j].next){
                int x = e[j].v;
                if(!vst[x] && dist[v] + e[j].w < dist[x]){
                    dist[x] = dist[v] + e[j].w;
                }
            }
        }
    }
    
    bool dijkstra(int s){
        memset(vst,0,sizeof(vst));
        memset(dist,0x3f3f3f3f,sizeof(dist));
        priority_queue<node> min_heap;
        dist[s] = 0;
        min_heap.push(node(s,0));
        while(!min_heap.empty()){
            int v = min_heap.top().u;
            min_heap.pop();
            if(vst[v]) continue;
            vst[v] = true;
            for(int j=p[v];j!=-1;j++){
                int x = e[j].v;
                if(!vst[x] && dist[v] + e[j].w < dist[x]){
                    dist[x] = dist[v] + e[j].w;
                    min_heap.push(node(x,dist[x]));
                }
            }
        }
        return true;
    }

### 4.tarjan ###

#include<bits/stdc++.h>
    using namespace std;
    
    
    const int maxn = 1e5+5;
    vector<int> g[maxn];
    int belong[maxn],scc = 0;
    int idx = 0;
    int dfn[maxn],low[maxn];
    bool ins[maxn];
    stack<int> s;
    
    void tarjan(int u){
        dfn[u] = low[u] = ++idx;
        s.push(u);
        ins[u] = 1;
        for(int i=0;i<g[u].size();i++){
            int v = g[u][i];
            if(!dfn[v]){
                tarjan(v);
                low[u] = min(low[u],low[v]);
            }else if(ins[v]){
                low[u] = min(low[u],dfn[v]);
            }
        }
        int vv;
        if(dfn[u] == low[u]){
            ++scc;
            do{
                vv = s.top();
                belong[vv] = scc;
                ins[vv] = false;
                s.pop();
            }while(vv != u);
        }
    }
    
    
    int main(){
        int n,m;
        cin>>n>>m;
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        idx = 0;
        for(int i=1;i<=m;i++){
            int u,v;
            cin>>u>>v;
            g[u].push_back(v);
        }
        for(int i=1;i<=n;i++){
            if(!dfn[i]){
                tarjan(i);
            }
        }
        for(int i=1;i<=scc;i++){
            cout<<"block "<<i<<": ";
            for(int j=1;j<=n;j++){
                if(belong[j] == i){
                    cout<<j<<" ";
                }
            }
            cout<<endl;
        }
        return 0;
    }
    /*
    4 4
    1 2
    2 3
    3 1
    2 4
    */

转载于:https://www.cnblogs.com/fisherss/p/10914820.html