leetcode 261-Graph Valid Tree(medium)(BFS, DFS, Union find)

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.

这道题主要就是判断1.是否有环路 2. 是否是连通图

可以用DFS, BFS 和 Union find,union find最合适。

对于DFS和BFS,首先都是建立adjacent list,把edges连接的所有情况加入邻接链表,注意需要对称加入,对于[a,b],要对a加入b,对b加入a。都可以用visited来记录是否遍历过。

1. BFS

bfs基本都是用queue实现,首先加入第一个点,每次poll出一个点,对其邻接链表遍历,入队,注意要将该点从其遍历到的邻接链表的点的邻接链表中删去,保证一条边不会来回走两次(为什么前面要对称加入而这里又要删去一边,因为不知道点之间联通的情况是怎么样的,在进行遍历的时候可能是从a->b的方向也可能相反,如果只加一个,在连通图遍历的时候本来连着的边会断掉)。用count记录连入连通图的点的个数,最后和n比。

再次提醒,对于list之类get到的点,都是object,不是int,在赋值给int时要(int),在用remove时,注意remove掉的是object,不能是int,remove(int index),remove(object ob),这两种要区分开,这里是要remove掉这个对象,所以要加(Integer)。

class Solution {
    public boolean validTree(int n, int[][] edges) {
        if(n==0) return false;
        List[] list=new List[n];
        for(int i=0;i<n;i++){
            list[i]=new ArrayList<Integer>();
        }
        for(int[] pair:edges){
            list[pair[0]].add(pair[1]);
            list[pair[1]].add(pair[0]);
        }
        Queue<Integer> queue=new LinkedList<>();
        queue.offer(0);
        boolean[] visited=new boolean[n];
        int count=1;
        while(!queue.isEmpty()){
            int a=queue.poll();
            if(visited[a]) return false;
            visited[a]=true;
            for(int i=0;i<list[a].size();i++){
                int m=(int)list[a].get(i);//注意要转int
                queue.offer(m);
                count++;
                list[m].remove((Integer)a);//注意要加(Integer),要不然是被认为是index,删除
            }
        }
        return count==n;
    }
}

2.DFS

dfs中需要记录pre,来避免a->b->a这样的遍历,从而被当成是环路。

class Solution {
    public boolean validTree(int n, int[][] edges) {
        if(n==0) return false;
        List[] list=new List[n];
        for(int i=0;i<n;i++){
            list[i]=new ArrayList<Integer>();
        }
        for(int[] pair:edges){
            list[pair[0]].add(pair[1]);
            list[pair[1]].add(pair[0]);
        }
        boolean[] visited=new boolean[n];
        if(dfs(list, visited, 0,-1)) return false;
        for(int i=0;i<n;i++){
            if(!visited[i]) return false;
        }
        return true;
    }
    public boolean dfs(List[] list, boolean[] visited, int id, int pre){
        if(visited[id]) return true;
        visited[id]=true;
        for(int i=0;i<list[id].size();i++){
            if(pre==(int)list[id].get(i)) continue;
            if(dfs(list, visited, (int)list[id].get(i), id)) return true;
        }
        return false;
    }
}

3. Union Find

用count记录连通图的个数,每并一次说明少一个分裂块,如果最后变为1,说明全部连通。

class Solution {
    public boolean validTree(int n, int[][] edges) {
        int[] connect=new int[n];
        if(edges.length!=n-1) return false;
        for(int i=0;i<n;i++){
            connect[i]=i;
        }
        int count=n;
        for(int i=0;i<edges.length;i++){
            int a=findroot(connect,edges[i][0]);
            int b=findroot(connect,edges[i][1]);
            if(a==b) return false;
            count--;
            connect[b]=a;
        }
        return count==1;
    }
    public int findroot(int[] connect, int id){
        while(connect[id]!=id) id=connect[id];
        return id;
    }
}

原文地址:https://www.cnblogs.com/yshi12/p/9734559.html

时间: 09-28

leetcode 261-Graph Valid Tree(medium)(BFS, DFS, Union find)的相关文章

[LeetCode#261] Graph Valid Tree

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. For example: Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], r

261. Graph Valid Tree

也是卡了好多天的题目 主要就是介绍了union-find的算法,用于检查Undirected graph有没有环 http://www.geeksforgeeks.org/union-find/ 1 public boolean validTree(int n, int[][] edges) { 2 int[] parent = new int[n]; 3 Arrays.fill(parent, -1); 4 for(int i = 0; i < edges.length ; i++) { 5

leetcode 222 Count Complete Tree Nodes (计算完全二叉树节点数)

1. 问题描述 计算完全二叉树的节点数.对于完全二叉树的定义可参考wikipedia上面的内容. 2. 方法与思路 最简单也最容易想到的方法就是使用递归,分别递归计算左右子树的节点数的和.但此方法最容易超时,一般不可取. int countNodes(TreeNode* root) { if(root == NULL) return 0; else if(root->left == NULL) return 1; return countNodes(root->left) + countNod

hdu4707 Pet(bfs &amp; dfs,vector)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4707 [题意]:linji的仓鼠丢了,他要找回仓鼠,他在房间0放了一块奶酪,然后给出房间的相邻关系,相邻的房间距离为1,题目给出奶酪能吸引仓鼠的最大距离 D,然后求出有多少房间可能是仓鼠所在的位置,也就是求有多少个房间距离 房间0 的距离 大于D. [分析] 网上有很多dfs的代码,我认为大多都有错误,他们的代码都默认了这一条件: 输入相邻的两个房间, 先输入的房间 距离房间0最近,然而题目并没说他

[LeetCode] Sum Root to Leaf Numbers(bfs)

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents the number 123. Find the total sum of all root-to-leaf numbers. For example, 1 / 2 3 T

[LeetCode] Subsets (bfs的vector实现)

Given a set of distinct integers, S, return all possible subsets. Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. For example, If S = [1,2,3], a solution is: [ [3], [1], [2], [1,2,3], [

HDU 4856 Tunnels(BFS+状压DP)

HDU 4856 Tunnels 题目链接 题意:给定一些管道,然后管道之间走是不用时间的,陆地上有障碍,陆地上走一步花费时间1,求遍历所有管道需要的最短时间,每个管道只能走一次 思路:先BFS预处理出两两管道的距离,然后状态压缩DP求解,dp[s][i]表示状态s,停在管道i时候的最小花费 代码: #include <cstdio> #include <cstring> #include <queue> #include <algorithm> using

hdu 1242:Rescue(BFS广搜 + 优先队列)

Rescue Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other) Total Submission(s) : 14   Accepted Submission(s) : 7 Font: Times New Roman | Verdana | Georgia Font Size: ← → Problem Description Angel was caught by the MOLIGPY

迷宫的最短路径(BFS的简单应用)

[题目简述]:给定一个大小为n*m的迷宫.迷宫由通道和墙壁组成,每一步可以向邻接的上下左右四格的通道移动.请求出起点到终点所需的最小步数.(注:本题假定从起点一定可以移动到终点) 如图: #S######.# ......#..# .#.##.##.# .#........ ##.##.#### ....#....# .#######.# ....#..... .####.###. ....#...G# [分析]:广度优先搜索是由近及远的搜索,所以在这个问题中采用BFS很合适,只要注意访问过的位