用并查集数出有几块
合并完所有关系之后,补全代码数出一共有几块。 做法:每个人各自 find 一次,数出有几个不同的根。
两个人到底连不连得通
补全 connected:判断两个人在不在同一块里。 把两个判断拼起来输出:阿岚和南风、阿岚和北辰,中间用 / 隔开。
一个够用的图至少要有哪几样
手写一张够用的图,至少要有【0】。
遍历和并查集各解决什么
图遍历和并查集,分工是【0】。
这张图有几个顶点几条边
运行下面这段程序: NAMES = ["阿岚", "小满", "阿泰", "南风", "北辰"] EDGES = [("阿岚&qu
第一步:把邻接表建出来
最终作品第一步:写出 build_adj(无向边两头各记一次)。 建好之后输出阿泰有几个邻居。
第二步:接上遍历
加上 BFS,把两个起点的结果拼起来输出:从阿岚出发能到几个、从北辰出发能到几个,中间用 / 隔开。
第三步:接上并查集
写出 find(带路径压缩)和 union,把四条关系全合并进去。 输出一共有几块。
第四步:两种办法互相印证
遍历数出来的块数,应该和并查集数出来的完全一样。 把两个结果拼起来输出(用 / 隔开):遍历数出的块数 / 并查集数出的块数。
交付:两种表示 + 遍历 + 并查集
这是这条路线的最终作品。把邻接表、邻接矩阵、BFS、并查集全写出来,然后一次验完五条: 邻接表里阿泰有 3 个邻居 邻接矩阵是对称的,而且 1 的个数是 8 从阿岚 BFS 能到 4 个人,从北辰只能到 1 个 并查集数出来是 2 块,和遍