261. Graph Valid Tree

Jinkey 发布于2019-08-16 10:29 / 984人阅读

摘要：题目链接检查图的连通性及是否有环，可以，，从一个点出发看能不能遍历所有的点，同时来检查是否有环。还可以用检查是否有环，最后看的数量是否等于来判断是不是。

261. Graph Valid Tree

题目链接：https://leetcode.com/problems...

检查图的连通性及是否有环，可以dfs，bfs，从一个点出发看能不能遍历所有的点，同时visited来检查是否有环。还可以用union find检查是否有环，最后看edge的数量是否等于n-1来判断是不是spinning tree。

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        if(edges.length != n - 1) return false;
        
        map = new int[n];
        Arrays.fill(map, -1);
        // union find
        for(int[] edge : edges) {
            int root1 = find(edge[0]);
            int root2 = find(edge[1]);
            // if connected before, there is a cycle
            if(root1 == root2) return false;
            // union
            map[root1] = root2;
        }
        return true;
    }
    int[] map;
    
    private int find(int child) {
        while(map[child] != -1) child = map[child];
        return child;
    }
}

dfs注意要保留parent指针，这样防止出现u->v之后又返回查一遍

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        // build graph
        build(edges, n);
        // store visited node
        Set visited = new HashSet();
        // dfs from 0, to check if visited all nodes and if cycle
        if(dfs(visited, 0, -1)) return false;
        return visited.size() == n;
    }
    
    // adjacent list to represent graph
    List> graph;
    private void build(int[][] edges, int n) {
        graph = new ArrayList();
        for(int i = 0; i < n; i++) graph.add(new HashSet());
        for(int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
    }
    
    private boolean dfs(Set visited, int u, int parent) {
        // has cycle
        if(visited.contains(u)) return true;
        visited.add(u);
        for(int v : graph.get(u)) {
            if(v == parent) continue;
            if(dfs(visited, v, u)) return true;
        }
        return false;
    }
}

bfs同样要要注意避免走重复路经的问题，遍历过的点就删掉。

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        // build graph
        build(edges, n);
        // store visited node
        Set visited = new HashSet();
        // bfs from 0, to check if visited all nodes and if cycle
        return bfs(visited, n);
    }
    
    // adjacent list to represent graph
    List> graph;
    private void build(int[][] edges, int n) {
        graph = new ArrayList();
        for(int i = 0; i < n; i++) graph.add(new HashSet());
        for(int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
    }
    
    private boolean bfs(Set visited, int n) {
        Queue q = new LinkedList();
        q.offer(0);
        while(!q.isEmpty()) {
            int u = q.poll();
            if(visited.contains(u)) return false;
            visited.add(u);
            for(int v : graph.get(u)) {
                q.offer(v);
                // remove parent, avoid duplicate
                graph.get(v).remove(u);
            }
        }
        
        return visited.size() == n;
    }
}

GPU云服务器云服务器 graph graph编程语言 Valid valid?file

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69875.html

[Leetcode] Graph Valid Tree 图与树

摘要：这样就将一个集合的节点归属到同一个集合号下了。最后如果并查集中只有一个集合，则说明可以构建树。 Graph Valid Tree Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check w...

luqiuwen 2019-08-14 12:36 评论0 收藏0
[Leetcode] Graph Valid Tree 判断一个图是否为树

摘要：只有一个连通分量还没有环，就是树，无根树。无向图边的两端是对称的，无向图讲究连通这个概念，没有方向，没有拓扑，很像集合，所以非常适合用并查集来解决。并查集写法参考注意方法用找的老大哥，合并的是的老大哥。 Graph Valid Tree Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each...

xbynet 2019-08-14 14:04 评论0 收藏0
[LeetCode] Graph Valid Tree [Union Find]

Problem Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. Example Given n = 5 and...

104828720 2019-08-14 15:10 评论0 收藏0
【LC总结】Union Find系列(Num of Islands I&II/Graph V

摘要：不得不说，对于这道题而言，是一种很木讷的模板。主函数按矩阵大小建立一个类进行后续操作一个结点用来连接边角不可能被围绕的一个函数对矩阵元素进行结点线性化。同理，，，在主函数中初始化后调用。 Surrounded Regions Problem Given a 2D board containing X and O (the letter O), capture all regions s...

bergwhite 2019-08-14 15:51 评论0 收藏0
vue+iview之select和时间日期的使用

摘要：实现从后台获取数据，并赋值默认值，同时也可以对选框进行更改，即实现双向绑定使用和方式实现双向绑定，如下请选择开始时间和结束时间获取默认时间将后台传回的默认时间数据放在时间选择框内按照后台传回的数据，将斜杠前的时间作为初始时间按照实现从后台获取数据，并赋值默认值，同时也可以对选框进行更改，即实现双向绑定 1、使用value和on-change方式实现双向绑定，html如下： js...

tainzhi 2019-08-23 16:03 评论0 收藏0