代码随想录-算法训练营day19【休息，复习与总结】

时间：2024-04-22 07:09:34

代码随想录-035期-算法训练营【博客笔记汇总表】-****博客

●day 19 周日休息（4.21）

目录

图论

并查集理论基础

1971_寻找图中是否存在路径

0684_冗余连接

0685_冗余连接II

图论

并查集理论基础

并查集常用来解决连通性问题。

大白话就是当我们需要判断两个元素是否在同一个集合里的时候，我们就要想到用并查集。

并查集主要有三个功能。

  1. 寻找根节点，函数：find(int u)，也就是判断这个节点的祖先节点是哪个；
  2. 将两个节点接入到同一个集合，函数：join(int u, int v)，将两个节点连在同一个根节点上；
  3. 判断两个节点是否在同一个集合，函数：isSame(int u, int v)，就是判断两个节点是不是同一个根节点。
int n = 1005; //n根据题目中节点数量而定，一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); //C++里的一种数组结构
vector<int> rank = vector<int> (n, 1); //初始每棵树的高度都为1

//并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
        rank[i] = 1; // 也可以不写
    }
}

//并查集里寻根的过程
int find(int u) {
    return u == father[u] ? u : find(father[u]);// 注意这里不做路径压缩
}

//判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

//将v->u 这条边加入并查集
void join(int u, int v) {
    u = find(u); //寻找u的根
    v = find(v); //寻找v的根

    if (rank[u] <= rank[v]) father[u] = v; //rank小的树合入到rank大的树
    else father[v] = u;

    //如果两棵树高度相同，则v的高度+1，因为上面 if (rank[u] <= rank[v]) father[u] = v; 注意是 <=
    if (rank[u] == rank[v] && u != v) rank[v]++;
}

1971_寻找图中是否存在路径

package com.question.solve.leetcode.programmerCarl._12_graphTheory;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class _1971_寻找图中是否存在路径 {
}

class Solution1971 {
    int[] father;

    public boolean validPath(int n, int[][] edges, int source, int destination) {
        father = new int[n];
        init();
        for (int i = 0; i < edges.length; i++) {
            join(edges[i][0], edges[i][1]);
        }
        return isSame(source, destination);
    }

    //并查集初始化
    public void init() {
        for (int i = 0; i < father.length; i++) {
            father[i] = i;
        }
    }

    //并查集里寻根的过程
    public int find(int u) {
        if (u == father[u]) {
            return u;
        } else {
            father[u] = find(father[u]);
            return father[u];
        }
    }

    //判断 u 和 v是否找到同一个根
    public boolean isSame(int u, int v) {
        u = find(u);
        v = find(v);
        return u == v;
    }

    //将v->u 这条边加入并查集
    public void join(int u, int v) {
        u = find(u); //寻找u的根
        v = find(v); //寻找v的根

        //如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
        if (u == v) return;

        father[v] = u;
    }
}

class Solution1971_2 {
    //方法一：广度优先搜索
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        for (int[] edge : edges) {
            int x = edge[0], y = edge[1];
            adj[x].add(y);
            adj[y].add(x);
        }
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new ArrayDeque<Integer>();
        queue.offer(source);
        visited[source] = true;
        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            if (vertex == destination) {
                break;
            }
            for (int next : adj[vertex]) {
                if (!visited[next]) {
                    queue.offer(next);
                    visited[next] = true;
                }
            }
        }
        return visited[destination];
    }
}

class Solution1971_3 {
    //方法二：深度优先搜索
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        for (int[] edge : edges) {
            int x = edge[0], y = edge[1];
            adj[x].add(y);
            adj[y].add(x);
        }
        boolean[] visited = new boolean[n];
        return dfs(source, destination, adj, visited);
    }

    public boolean dfs(int source, int destination, List<Integer>[] adj, boolean[] visited) {
        if (source == destination) {
            return true;
        }
        visited[source] = true;
        for (int next : adj[source]) {
            if (!visited[next] && dfs(next, destination, adj, visited)) {
                return true;
            }
        }
        return false;
    }
}

0684_冗余连接

package com.question.solve.leetcode.programmerCarl._12_graphTheory;

public class _0684_冗余连接 {
}

class Solution0684 {
    private int n; //节点数量：3 到 1000
    private int[] father;

    public Solution0684() {
        n = 1005;
        father = new int[n];

        //并查集初始化
        for (int i = 0; i < n; ++i) {
            father[i] = i;
        }
    }

    //并查集里寻根的过程
    private int find(int u) {
        if (u == father[u]) {
            return u;
        }
        father[u] = find(father[u]);
        return father[u];
    }

    //将 v->u 这条边加入并查集
    private void join(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return;
        father[v] = u;
    }

    //判断 u 和 v 是否找到同一个根，本题用不上
    private Boolean same(int u, int v) {
        u = find(u);
        v = find(v);
        return u == v;
    }

    public int[] findRedundantConnection(int[][] edges) {
        for (int i = 0; i < edges.length; i++) {
            if (same(edges[i][0], edges[i][1])) {
                return edges[i];
            } else {
                join(edges[i][0], edges[i][1]);
            }
        }
        return null;
    }
}

class Solution0684_2 {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        int[] parent = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
        for (int i = 0; i < n; i++) {
            int[] edge = edges[i];
            int node1 = edge[0], node2 = edge[1];
            if (find(parent, node1) != find(parent, node2)) {
                union(parent, node1, node2);
            } else {
                return edge;
            }
        }
        return new int[0];
    }

    public void union(int[] parent, int index1, int index2) {
        parent[find(parent, index1)] = find(parent, index2);
    }

    public int find(int[] parent, int index) {
        if (parent[index] != index) {
            parent[index] = find(parent, parent[index]);
        }
        return parent[index];
    }
}

0685_冗余连接II

package com.question.solve.leetcode.programmerCarl._12_graphTheory;

import java.util.ArrayList;

public class _0685_冗余连接II {
}

class Solution0685 {
    private static final int N = 1010;  //如题：二维数组大小的在3到1000范围内
    private int[] father;

    public Solution0685() {
        father = new int[N];

        //并查集初始化
        for (int i = 0; i < N; ++i) {
            father[i] = i;
        }
    }

    //并查集里寻根的过程
    private int find(int u) {
        if (u == father[u]) {
            return u;
        }
        father[u] = find(father[u]);
        return father[u];
    }

    //将v->u 这条边加入并查集
    private void join(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return;
        father[v] = u;
    }

    //判断 u 和 v是否找到同一个根，本题用不上
    private Boolean same(int u, int v) {
        u = find(u);
        v = find(v);
        return u == v;
    }

    /**
     * 初始化并查集
     */
    private void initFather() {
        //并查集初始化
        for (int i = 0; i < N; ++i) {
            father[i] = i;
        }
    }

    /**
     * 在有向图里找到删除的那条边，使其变成树
     *
     * @param edges
     * @return 要删除的边
     */
    private int[] getRemoveEdge(int[][] edges) {
        initFather();
        for (int i = 0; i < edges.length; i++) {
            if (same(edges[i][0], edges[i][1])) { // 构成有向环了，就是要删除的边
                return edges[i];
            }
            join(edges[i][0], edges[i][1]);
        }
        return null;
    }

    /**
     * 删一条边之后判断是不是树
     *
     * @param edges
     * @param deleteEdge 要删除的边
     * @return true：是树，false：不是树
     */
    private Boolean isTreeAfterRemoveEdge(int[][] edges, int deleteEdge) {
        initFather();
        for (int i = 0; i < edges.length; i++) {
            if (i == deleteEdge) continue;
            if (same(edges[i][0], edges[i][1])) {//构成有向环了，一定不是树
                return false;
            }
            join(edges[i][0], edges[i][1]);
        }
        return true;
    }

    public int[] findRedundantDirectedConnection(int[][] edges) {
        int[] inDegree = new int[N];
        for (int i = 0; i < edges.length; i++) {
            //入度
            inDegree[edges[i][1]] += 1;
        }

        //找入度为2的节点所对应的边，注意要倒序，因为优先返回最后出现在二维数组中的答案
        ArrayList<Integer> twoDegree = new ArrayList<Integer>();
        for (int i = edges.length - 1; i >= 0; i--) {
            if (inDegree[edges[i][1]] == 2) {
                twoDegree.add(i);
            }
        }

        //处理图中 情况1 和 情况2
        //如果有入度为2的节点，那么一定是两条边里删一个，看删哪个可以构成树
        if (!twoDegree.isEmpty()) {
            if (isTreeAfterRemoveEdge(edges, twoDegree.get(0))) {
                return edges[twoDegree.get(0)];
            }
            return edges[twoDegree.get(1)];
        }

        //明确没有入度为2的情况，那么一定有有向环，找到构成环的边返回就可以了
        return getRemoveEdge(edges);
    }
}

相关文章