Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >图:拓扑排序/Union Find高频题

图:拓扑排序/Union Find高频题

原创
作者头像
王脸小
修改于 2020-07-31 02:39:16
修改于 2020-07-31 02:39:16
84000
代码可运行
举报
文章被收录于专栏:王漂亮王漂亮
运行总次数:0
代码可运行

Union Find

解决动态连通性一类问题

并查集(Union-Find)算法介绍 link

并查集(参考leetcode323题)link

UnionFind Class

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class UnionFind:
    def __init__(self, n):
        self.count = n
        self.parent = [i for i in range(n)]
    
    def find(self, idx):
        if self.parent[idx] != idx:
            self.parent[idx] = self.find(self.parent[idx])
        return self.parent[idx]
    
    def union(self, i, j):
        i_pos = self.find(i)
        j_pos = self.find(j)
        if i_pos != j_pos:
            self.parent[i_pos] = j_pos
            self.count -= 1
            
    def Count(self):
        return self.count

Find问题:最后idx=parent,为什么不能return idx

200. 岛屿数量

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
Input:
11110
11010
11000
00000

Output: 1

Solution

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution:
    def numIslands(self, grid):
        row = len(grid)
        col = len(grid[0]) if row else 0
    
        if not row or not col: return 0
        
        dummy_node = row*col
        uf = UnionFind(dummy_node+1)
        
        for i in range(row):
            for j in range(col):
                if grid[i][j] == "0":
                    uf.union(dummy_node, i*col+j)
                if grid[i][j] == "1":
                    for x,y in [(0,1), (1,0)]:
                        if i+x<row and j+y<col and grid[i+x][j+y] == '1':
                            uf.union((i+x)*col+(j+y), (i*col)+j)
                            
        return uf.Count()-1

323. 无向图中连通分量的数目

给定编号从 0 到 n-1 的 n 个节点和一个无向边列表(每条边都是一对节点),请编写一个函数来计算无向图中连通分量的数目。

示例 1:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入: n = 5 和 edges = [[0, 1], [1, 2], [3, 4]]

     0          3
     |          |
     1 --- 2    4 

输出: 2

示例 2:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入: n = 5 和 edges = [[0, 1], [1, 2], [2, 3], [3, 4]]

     0           4
     |           |
     1 --- 2 --- 3

输出:  1

注意: 你可以假设在 edges 中不会出现重复的边。而且由于所以的边都是无向边,[0, 1] 与 [1, 0]  相同,所以它们不会同时在 edges 中出现。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class UnionFind:
    def __init__(self, n):
        self.count = n
        self.parent = [i for i in range(n)]

    def Find(self, p):
        if p != self.parent[p]:
            self.parent[p] = self.parent[self.parent[p]]
            p = self.parent[p]
        return self.parent[p]

    def Union(self, p, q):
        p_root = self.Find(p)
        q_root = self.Find(q)

        self.parent[p_root] = q_root
        self.count -= 1

    def IsConnected(self, p, q):
        return self.Find(p) == self.Find(q)

    def Count(self):
        return self.count

    
class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        uf = UnionFind(n)
        for i,j in edges:
            uf.Union(i,j)
            
        return uf.Count()

一遍过的朋友~~

拓扑排序

Workflow:

1. 遍历构造indegree和outdegree

2. 遍历indegree收集indegree为0的节点 -> q

3. while q.pop, 减少当前node的outdegree中节点的indegree,当indegree为零append到q

4. 知道遍历完所有节点,return

207. 课程表

Course Schedule

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
Input: 2, [[1,0]] 
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.

Example 2:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0, and to take course 0 you should
             also have finished course 1. So it is impossible.

Note:

  1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  2. You may assume that there are no duplicate edges in the input prerequisites.

Solution

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        indegree = [0 for _ in range(numCourses)]
        outdegree = [[] for _ in range(numCourses)]
        
        for nex, pre in prerequisites:
            indegree[nex] += 1
            outdegree[pre].append(nex)
            
        q = []
        for i in range(len(indegree)):
            if indegree[i] == 0: q.append(i)
            
        count = 0
        while q:
            pre = q.pop()
            count += 1
            for nex in outdegree[pre]:
                indegree[nex] -= 1
                if not indegree[nex]: q.append(nex)
                    
        return count == numCourses

之前做的,构造图比较直接,然后拓扑排序

210. 课程表 II

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Example 1:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
Input: 2, [[1,0]] 
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished   
             course 0. So the correct course order is [0,1] .

Example 2:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both     
             courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. 
             So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .

Solution

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        indegree = [0 for _ in range(numCourses)]
        outdegree = [[] for _ in range(numCourses)]
        
        for nex, pre in prerequisites:
            indegree[nex] += 1
            outdegree[pre].append(nex)
            
        q = []
        for i in range(len(indegree)):
            if indegree[i] == 0: q.append(i)
            
        res = []
        while q:
            pre = q.pop()
            res.append(pre)
            for nex in outdegree[pre]:
                indegree[nex] -= 1
                if not indegree[nex]: q.append(nex)
                    
        return res if len(res) == numCourses else []

269. 火星词典

Alien Dictionary

现有一种使用字母的全新语言,这门语言的字母顺序与英语顺序不同。

假设,您并不知道其中字母之间的先后顺序。但是,会收到词典中获得一个 不为空的 单词列表。因为是从词典中获得的,所以该单词列表内的单词已经 按这门新语言的字母顺序进行了排序

您需要根据这个输入的列表,还原出此语言中已知的字母顺序。

示例 1:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入:
[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

输出: "wertf"

示例 3:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入:
[
  "z",
  "x",
  "z"
] 

输出: "" 

解释: 此顺序是非法的,因此返回 ""

注意:

  1. 你可以默认输入的全部都是小写字母
  2. 假如,a 的字母排列顺序优先于 b,那么在给定的词典当中 a 定先出现在 b 前面
  3. 若给定的顺序是不合法的,则返回空字符串即可
  4. 若存在多种可能的合法字母顺序,请返回其中任意一种顺序即可

Solution

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
from collections import defaultdict
class Solution(object):
    def alienOrder(self, words):
        if not words or not words[0]: return ""
        indegree = defaultdict(int)
        outdegree = defaultdict(set)
        
        res = ""
        
        for i in range(len(words)):
            for j in range(i+1, len(words)):
                idx = 0
                while idx < len(words[i]) and idx < len(words[j]) and words[i][idx] == words[j][idx]:
                    idx += 1
                if idx < len(words[i]) and idx < len(words[j]) and words[j][idx] not in outdegree[words[i][idx]]:
                    outdegree[words[i][idx]].add(words[j][idx])
                    indegree[words[j][idx]] += 1
                    indegree[words[i][idx]] += 0

                    
        q = []
        for k,v in indegree.items():
            if not v: 
                q.append(k)
                res += k
                
        while q:
            ch = q.pop()
            for next_ch in outdegree[ch]:
                indegree[next_ch] -= 1
                if not indegree[next_ch]: 
                    q.append(next_ch)
                    res += next_ch
                    
        return res

自己写 ,但还有些edge case没过,如["z","z"]

思路:建图,key为前序,value为后继,然后拓扑排序逐个添加入度为零的节点。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
Board相关题
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
王脸小
2019/10/31
7910
算法题基本框架 - Python实现
通常情况下使用数组维护的并查集更省空间,因为直接定义了一个n条边的数组,使用下标来维护对应关系。但是遇到二维坐标时,用哈希维护的并查集更合适,因为可以把y映射到x取值范围外,使二维转化为一维。比如: 1584.连接所有点的最小费用
Ewdager
2021/01/29
3940
Python3刷题系列(九)
二叉搜索树中序遍历,前缀树,二分图,二叉树前序遍历,并查集,拓扑排序 目录: 1,Leetcode-230 2,Leetcode-208 3,Leetcode-785 4,Leetcode-144 5,Leetcode-513 6,Leetcode-684 7,Leetcode-207 8,Leetcode-110 1,Leetcode-230: # leetcode-230:二叉搜索树,中序遍历,beats 56.14% # Definition for a binary tree node. #
用户5473628
2019/08/08
3750
高频经典算法题汇总
注:一般要分为两段的链表的双指针slow,fast = head, head.next; 不需要分为两段的slow,fast = head, head
王脸小
2020/07/30
2.4K0
【python-leetcode207-拓扑排序】课程表
你这个学期必须选修 numCourse 门课程,记为 0 到 numCourse-1 。
西西嘛呦
2020/08/26
4680
算法细节系列(17):有向环检测&&拓扑排序
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/71719530
用户1147447
2019/05/26
7490
Data Structurestackheapheap的实现索引堆tree并查集图 Graph
堆的基本性质: ①堆中的某一个节点总是不小于或不大于其父节点的值。 ②堆总是一棵完全二叉树 比较经典的堆有二叉堆,费波纳茨堆等等。如果一棵二叉树最下层上的结点都集中在该层最左边的若干位置上,而在最后一层上,右边的若干结点缺失的二叉树,则此二叉树成为完全二叉树。
西红柿炒鸡蛋
2018/09/07
6990
Two Sigma:面试真题 - 编程(下)
量化投资与机器学习微信公众号,是业内垂直于量化投资、对冲基金、Fintech、人工智能、大数据等领域的主流自媒体。公众号拥有来自公募、私募、券商、期货、银行、保险、高校等行业30W+关注者,荣获2021年度AMMA优秀品牌力、优秀洞察力大奖,连续2年被腾讯云+社区评选为“年度最佳作者”。 上一起,QIML为大家分享几道有关Two Sigma面试的计算真题。今天,我们主要为大家分享几道编程真题。 Two Sigma:面试真题(上) 量化对冲基金技术面试中一般都会有pair coding的部分,主要是测试候选
量化投资与机器学习微信公众号
2022/09/22
1K0
Two Sigma:面试真题 - 编程(下)
LeetCode-算法- 广度和深度优先搜索-第20天
给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外,你可以假设该网格的四条边均被水包围。
布衣者
2021/09/07
2440
Leetcode|BFS+DFS拓扑排序|210. 课程表 II
1 BFS拓扑排序 class Solution { public: vector<vector<int>> edges; // 邻接矩阵 vector<int> indegree; // 入度表 vector<int> res; vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) { edges.resize(numCou
SL_World
2022/01/10
2250
Leetcode|BFS+DFS拓扑排序|210. 课程表 II
算法沉淀——拓扑排序
在下面的这张图中,1这个点的入度就是0,2这个点的入度就是2,因为有两条有向线段指向2这个点。
用户11316056
2024/10/16
1190
算法沉淀——拓扑排序
【python刷题】并查集
这里借用百度百科的一句话:并查集是一种树型的数据结构,用于处理一些不相交集合(disjoint sets)的合并及查询问题。常常在使用中以森林来表示。假设现在有一个武林大会,包含了少林、峨嵋、武当等门派,通过并查集就可以将每个人归类到自己的门派中。
西西嘛呦
2021/01/29
7910
【图解】拓扑排序(210. 课程表 II)
这是一个典型的拓扑排序题目, 对拓扑排序不熟悉的,可以看下这个文章 - 揭开「拓扑排序」的神秘面纱,可以说讲的非常详细了。
lucifer210
2020/05/25
6210
【图解】拓扑排序(210. 课程表 II)
【python-leetcode210-拓扑排序】课程表Ⅱ
在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们: [0,1]
西西嘛呦
2020/08/26
5710
【python-leetcode210-拓扑排序】课程表Ⅱ
BFS:解决拓扑排序问题
要知道什么拓扑排序我们首先要知道什么是有向无环图,有向无环图我们看名字其实就很容易理解,有向就是有方向,无环就是没有环形结构,这里我们展示一下有向无环图和有向有环图:
用户11305458
2024/10/09
1930
BFS:解决拓扑排序问题
【C++】拓扑排序(BFS)
通过入度和出入我们可以判断活动的进行顺序,活动度数为0的活动先进行没进行完后,将该活动的出度清空,下一个入度为0的节点就是该节点之后要进行的活动,以此类推,直到最后没有活动节点,如果只存在有一个入度的节点(成环)。
啊QQQQQ
2024/11/19
1630
【C++】拓扑排序(BFS)
LeetCode 200:岛屿数量 Number of Islands
给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
爱写bug
2019/09/02
7380
文心一言 VS 讯飞星火 VS chatgpt (280)-- 算法导论20.4 1题
一、假设 CONNECTED-COMPONENTS 作用于一个无向图 G=(V,E),这里V={a,b,c,d,e,f,g,h,i,j,k},且 E 中的边以如下的顺序处理:(d,i),(f,k),(g,i),(b,g),(a,h),(i,j),(d,k),(b,j),(d,f),(g,j),(a,e)。请列出在每次执行完第3~5行后各连通分量的顶点。如果要写代码,请用go语言。
福大大架构师每日一题
2024/08/16
1040
文心一言 VS 讯飞星火 VS chatgpt (280)-- 算法导论20.4 1题
2023-08-08:给你一棵 n 个节点的树(连通无向无环的图) 节点编号从 0 到 n - 1 且恰好有 n - 1 条边
其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边
福大大架构师每日一题
2023/08/29
2920
2023-08-08:给你一棵 n 个节点的树(连通无向无环的图) 节点编号从 0 到 n - 1 且恰好有 n - 1 条边
文心一言 VS 讯飞星火 VS chatgpt (345)-- 算法导论23.2 4题
四、假定图中的边权重全部为整数,且在范围$1 \sim |V|$内。在此种情况下,Kruskal算法最快能多快?如果边的权重取值范围在1到某个常数$W$之间呢?如果要写代码,请用go语言。
福大大架构师每日一题
2024/09/13
1320
文心一言 VS 讯飞星火 VS chatgpt (345)-- 算法导论23.2 4题
推荐阅读
相关推荐
Board相关题
更多 >
交个朋友
加入腾讯云官网粉丝站
蹲全网底价单品 享第一手活动信息
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验