LeetCode题解-07（简单图论）

目录
  • LeetCode题解
    • chap-17:图论
        • 1、岛屿数量
        • 2、课程表 拓扑排序
        • 3、课程表 II
        • 4、最小高度树 树形DP
        • 5、重新安排行程 欧拉回路
        • 6、除法求值
        • 7、省份数量 【朋友圈】
        • 8、冗余连接 【并查集】
        • 9、网络延迟时间
        • 10、判断二分图 【×】
        • 11、所有可能的路径 dfs
        • 12、等式方程的可满足性
        • 13、连接所有点的最小费用 【最小生成树】

LeetCode题解

chap-17:图论

1、岛屿数量

// 并查集+坐标变换
class UnionFind{
public:
    vector parent;
    UnionFind(int n){
        for(int i=0;i>& grid) {
        int dx[4]={-1,0,1,0}, dy[4]={0,1,0,-1};
        int n=grid.size(), m=grid[0].size();
        UnionFind UF(n*m);
        for(int i=0;i=0 && i+di < n && j+dj >=0 && 
                           j+dj < m && grid[i+di][j+dj]=='1'){
                            UF.Union(encode(i, j, m), encode(i+di, j+dj, m));
                        }
                    }
                }
            }
        }
        int ans=0;
        for(int i=0;i>& grid) {
        for(int i = 0;i>& g,int x,int y){
        g[x][y] = '*';        
        for(int i = 0;i<4;i++){
            int x_ = dx[i] + x, y_ = dy[i] + y;
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < g.size() && b >= 0 && b < g[a].size() && g[a][b] == '1')
            dfs(g,a, b);
        }
    }
};

2、课程表 拓扑排序

class Solution {
public:
    bool canFinish(int n, vector>& p) {
        vector in(n,0);
        vector> g(n);
        for(auto&t:p){
            g[t[1]].push_back(t[0]);
            in[t[0]]++;
        }
        queue q;
        vector f(n,false);
        for(int i=0;i

3、课程表 II

class Solution {
public:
    vector findOrder(int n, vector>& pres) {
        vector indegree(n,0);
        vector> g(n);
        for(auto &t:pres){
            g[t[1]].push_back(t[0]); indegree[t[0]]++;
        }
        queue q;
        for(int i=0;i vis(n,false);

        vector ans;
        while(q.size()){
            auto t=q.front();
            vis[t]=true;
            ans.push_back(t); q.pop();
            for(auto &c:g[t]){
                indegree[c]--;
                if(indegree[c]==0) q.push(c);
            }
        }
        for(auto c:vis) if(!c) return vector({});
        return ans;
    }
};

4、最小高度树 树形DP

// 树形模板
class Solution {
public:
    int n;
    vector>g;
    vector d1,d2,p1,up;
    void dfs1(int u,int father){ // 向下遍历
        for(auto x:g[u]){
            if(x==father) continue;
            dfs1(x,u);
            int d = d1[x]+1;
            if(d>=d1[u]){
                d2[u]=d1[u], d1[u]=d;
                p1[u]=x;
            }else if(d>d2[u]) d2[u]=d;
        }
    }
    void dfs2(int u,int father){ // 向上遍历
        for(auto x:g[u]){
            if(x==father) continue;
            if(p1[u]==x) up[x] = max(up[u], d2[u])+1;
            else up[x] = max(d1[u], up[u])+1;
            dfs2(x,u);
        }
    }
    vector findMinHeightTrees(int m, vector>& edges) {
        n=m; d1.resize(n); d2.resize(n); p1.resize(n); up.resize(n);
        g.resize(n);
        for(auto &t:edges) {
            g[t[0]].push_back(t[1]);
            g[t[1]].push_back(t[0]);
        }
        dfs1(0,-1);
        dfs2(0,-1);
        int mind=n-1;
        vector ans;
        for(int i=0;i t){
                ans = vector({});
                ans.push_back(i);
                mind = t;
            }else if(mind == t) ans.push_back(i);
        }
        return ans;
    }
};

// BFS
class Solution {
public:
    vector findMinHeightTrees(int n, vector>& edges) {
        if(n==1) return {0};
        vector degree(n);   //节点对应的出度
        vector> m(n);  //邻接表
        vector res; //结果
        for(auto &t:edges){
            degree[t[0]]++; degree[t[1]]++;
            m[t[0]].push_back(t[1]);
            m[t[1]].push_back(t[0]);
        }
        queue q;
        //最外层叶子节点入栈
        for(int i=0;i

5、重新安排行程 欧拉回路

class Solution {
public:
    vector ans;
    unordered_map> hash;
    vector findItinerary(vector>& tickets) {
        for(auto &t:tickets){
            hash[t[0]].insert(t[1]);
        }
        dfs("JFK");
        return vector(ans.rbegin(),ans.rend());
    }
    void dfs(string s){
        while(hash[s].size()){
            auto t=*hash[s].begin();
            hash[s].erase(hash[s].begin());
            dfs(t);
        }
        ans.push_back(s);
    }
};

6、除法求值

class Solution {
public:
    vector calcEquation(vector>& es, vector& vs, vector>& qs) {
        // floyed
        unordered_set hash;
        unordered_map> g;
        for(int i=0;i ans;
        for(auto q: qs) {
            auto a = q[0], b = q[1];
            if (g[a][b]) ans.push_back(g[a][b]);
            else ans.push_back(-1);
        }
        return ans;
    }
};

7、省份数量 【朋友圈】

// 并查集+坐标变换
class UnionFind{
public:
    vector parent;
    UnionFind(int n){
        for(int i=0;i>& isConnected) {
        int n=isConnected.size();        
        UnionFind Uf(n);
        for(int i=0;i

8、冗余连接 【并查集】

class Solution {
public:
    int find(vector&father, int id){
        if(father[id]==id) return id;
        father[id]=find(father,father[id]);
        return father[id];
    }
    vector findRedundantConnection(vector>& edges) {
        int n=edges.size();
        vector father(n+1);
        for(int i=0;i<=n;i++)father[i]=i;
        vector ans(2,0);
        for(auto &edge:edges){
            int fa=find(father,edge[0]), fb=find(father,edge[1]);
            if(fa==fb) ans[0]=edge[0], ans[1]=edge[1];
            father[fa]=fb;
        }
        return ans;
    }
};

9、网络延迟时间

class Solution {
public:
    int networkDelayTime(vector>& times, int n, int c) {
        int dp[n+1][n+1];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(i==j) dp[i][j]=0;
                else dp[i][j]=0x3f3f3f;
        for(auto &t:times) dp[t[0]][t[1]]=t[2];
        // floyd
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);    
        int ans=0;
        for(int i=1;i<=n;i++){
            if(dp[c][i]==0x3f3f3f) return -1;
            else ans=max(ans,dp[c][i]);
        }
        return ans;
    }
};

// spfa算法
class Solution {
public:
    static const int N=110, M=6010, INF=0x3f3f3f3f;
    int h[N], e[M], w[M], ne[M];
    int eidx,n;
    int dist[N];
    bool st[N];
    void add(int a,int b,int c){
        e[eidx]=b, w[eidx]=c, ne[eidx]=h[a], h[a]=eidx++;
    }
    void spfa(int start){
        queue q;
        q.push(start);
        dist[start]=0;
        while(q.size()){
            int t=q.front(); 
            q.pop();
            st[t]=false;
            for(int i=h[t];i!=-1;i=ne[i]){
                if (dist[e[i]] > dist[t] + w[i]){
                    dist[e[i]] = dist[t] + w[i];
                    if (!st[e[i]])
                    {
                        st[e[i]] = true;
                        q.push(e[i]);
                    }
                }
            }
        }
    }
    int networkDelayTime(vector>& times, int n_, int k) {
        memset(h,-1,sizeof h);
        eidx=0; n=n_;
        for(auto &t:times) add(t[0],t[1],t[2]);
        memset(dist,0x3f,sizeof dist);
        memset(st,0,sizeof st);
        spfa(k);
        int ans=0;
        for(int i=1;i<=n;i++){
            if(dist[i]==INF) return -1;
            else ans = max(ans,dist[i]);
        }
        return ans;
    }
};

10、判断二分图 【×】

class Solution {
public:
    bool isBipartite(vector>& graph) {
        int n=graph.size();        
        vector st(n,-1);
        for(int i=0;i>& graph, vector&st, int u,int c){
        st[u]=c;
        for(auto a:graph[u]){ 
            if(st[a] != -1) {
                if(st[a]==c) return false;
            }
            else if(!dfs(graph, st, a, 1-c)) return false;
        }
        return true;
    }
};

// bfs
class Solution {
public:
    bool bfs(int S, vector& color, const vector>& graph) {
        color[S] = 0;
        queue q; q.push(S);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto &v : graph[u]) {
                if (color[v] == color[u])
                    return false;
                if (color[v] == -1) {
                    color[v] = 1 - color[u];
                    q.push(v);
                }
            }
        }
        return true;
    }
    bool isBipartite(vector>& graph) {
        int n = graph.size();
        vector color(n, -1);
        for (int i = 0; i < n; i++)
            if (color[i] == -1) {
                if (!bfs(i, color, graph))
                    return false;
            }
        return true;
    }
};

11、所有可能的路径 dfs

class Solution {
public:
    int n;    
    vector f;
    vector path;
    vector> ans;
    vector> allPathsSourceTarget(vector>& graph) {
        n=graph.size();
        f.resize(n);
        dfs(graph,0);
        return ans;
    }
    void dfs(vector>& graph, int u){
        if(u == n-1 && !f[u]){
            path.push_back(u);
            ans.emplace_back(path);
            path.pop_back();
        }else if(!f[u]){
            f[u]=true;
            path.push_back(u);
            for(auto t:graph[u]){
                dfs(graph, t);
            }
            path.pop_back();
            f[u]=false;
        }
    }
};

12、等式方程的可满足性

class Solution {
public:
    int Find(vector& father, int id){
        if(father[id]==id) return id;
        father[id]=Find(father, father[id]);
        return father[id];
    }    
    bool equationsPossible(vector& equations) {
        vector father(26);
        for(int i=0;i<26;i++) father[i]=i;
        for(auto &eq:equations){
            int a = eq[0]-'a', b = eq[3]-'a';            
            if(eq[1]=='='){
            int fa=Find(father, a);
            int fb=Find(father, b);            
            father[fa]=fb;
            }
        }
        for(auto &eq:equations){
            int a = eq[0]-'a', b = eq[3]-'a';            
            if(eq[1]=='!'){
                int fa=Find(father, a);
                int fb=Find(father, b); 
                if(fa==fb) return false;
            }
        }
        return true;
    }
};

13、连接所有点的最小费用 【最小生成树】

class Solution {
private:
    int calc(vector &x, vector &y) {
        return abs(x[0] - y[0]) + abs(x[1] - y[1]);
    }

public:
    int minCostConnectPoints(vector>& points) {
        // prim算法
        const int n = points.size();
        vector vis(n, false);
        vector dis(n, INT_MAX);
        int ans = 0;
        dis[0] = 0;
        for (int i = 0; i < n; i++) {
            int mindis = INT_MAX;
            int m = -1;
            for (int j = 0; j < n; j++)
                if (!vis[j] && mindis > dis[j]) {
                    mindis = dis[j];
                    m = j;
                }
            vis[m] = true;
            ans += mindis;
            for (int j = 0; j < n; j++)
                dis[j] = min(dis[j], calc(points[m], points[j]));
        }
        return ans;
    }
};

[Go Back~](# LeetCode题解)

力扣

相关

力扣 16题 最接近的三数之和

力扣530题（二叉搜索树的最小绝对差）

力扣 - 剑指 Offer 24. 反转链表

力扣 - 剑指 Offer 28. 对称的二叉树

力扣 - 剑指 Offer 55 - I. 二叉树的深度

力扣 Leetcode 448. 找到所有数组中消失的数字 巧妙思路

力扣题目汇总（加一，旋转数组，整数反转）

力扣题目汇总（机器人返回原点，按奇偶排序，数字的补数)

力扣题目汇总（位1的个数，有效的字母异位词，检测大写字母）

力扣每天刷题(2)

力扣81、搜索旋转排序数组Ⅱ

1月5日力扣刷题

标签

一品网 冀ICP备14022925号-6