力扣-图论-4【算法学习day.54】

时间：2024-12-11 06:58:40

前言

###我做这类文章一个重要的目的还是给正在学习的大家提供方向和记录学习过程（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.连通网络的操作次数

题目链接:1319. 连通网络的操作次数 - 力扣（LeetCode）

题面:

分析:这题其实就是看图的个数，如果有两块图，那么只需要一根线，如果三块，需要两根.....，所以我们只需要求出图的个数和多余线的个数即可，这里我们采用并查集，遍历connections时，将两个节点通过find函数合并，但如果这两个节点早已合并，这样就相当于多出了一根线，且不需要做合并操作，之后我们遍历每个节点，看他们的父节点有多少个也就是有多少块图，这里用到Map哈希表，最后比较两数即可

代码:

class Solution {
    int[] parent;
    public int makeConnected(int n, int[][] connections) {
    parent =  new int[n];
    for(int i = 0;i<n;i++){
        parent[i] = i;
    }
    int count = 0;
    for(int[] arr:connections){
        int a = arr[0];
        int b = arr[1];
        if(isINALine(a,b)){
            count++;
        }else{
            union(a,b);
        }
    }
    int flag = -1;
    Map<Integer,Integer> map = new HashMap<>();
    for(int i = 0;i<n;i++){
        if(map.getOrDefault(find(i),-1)==-1){
            flag++;
            map.put(find(i),1);
        }
    }

    return count>=flag?flag:-1;

    }

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

    public void union(int a,int b){
        int pa = find(a);
        int pb = find(b);
        if(pa!=pb){
            parent[pa] = pb;
        }
    }

    public boolean isINALine(int a,int b){
        return find(a)==find(b);
    }
}

2.两个城市间路径的最小分数

题目链接:2492. 两个城市间路径的最小分数 - 力扣（LeetCode）

题面:

分析:1到n可能有多条路径，每条路径由多段路组成，而题目就是求路径中的最小段路的长，这题先采用并查集用基础数据将图初始化一下，我们在遍历数组roads的时候，可以利用Pair将当前路的长度，和在roads中的索引存一下，然后创建一个Pair数组，将pair对象存进去，然后我们排序这个数组，按照key也就是路的长度从小到大排，之后遍历这个pair数组，拿到索引，然后从roads中拿到这段路的两节点号，首先可以明确的是，这两个节点是相连的，例如a，b，如果a的并查集父节点等于1的，也等于n的，就表明a和b和1，n在一个图中，也就是在一条可达路径中，由于我们将pair数组的key从小到大排过序了，那么此时返回pair对象key即可，也就是最短路。 

代码:

class Solution {
    int[] parent;
    public int minScore(int n, int[][] roads) {
        parent = new int[n+1];
        for(int i = 1;i<=n;i++){
            parent[i] = i;
        }
        int m = roads.length;
        Pair<Integer,Integer>[] arr = new Pair[m];
        int count = 0;
        for(int[] brr:roads){
            int a = brr[0];
            int b = brr[1];
            union(a,b);
            Pair<Integer,Integer> p = new Pair<>(brr[2],count); 
            // System.out.println(p);
            arr[count] = p;
            count++;
        }
         Arrays.sort(arr, (o1, o2) -> o1.getKey()-o2.getKey());
         for(int i = 0;i<n;i++){
            int index = arr[i].getValue();
            int[] brr = roads[index];
            int a = brr[0];
            int b = brr[1];
            if(find(1)==find(a)&&find(n)==find(a)){
                return brr[2];
            }
         }
         return 0;

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

    public void union(int a,int b){
        int pa = find(a);
        int pb = find(b);
        if(pa!=pb){
            parent[pa] = pb;
        }
    }

    public boolean isInALine(int a,int b){
        return find(a)==find(b);
    }

}

后言

上面是力扣图论专题，下一篇是其他的习题，希望有所帮助，一同进步，共勉！

相关文章