Hey我的编程小伙伴们👋，今天我要和大家分享一道我在LeetCode上遇到的超有趣的题目——编号3067的在带权树网络中统计可连接服务器对数目。这是一道非常适合练习DFS和图的题目哦！🤓💻
邻接图是什么？
在我们深入题目之前，先来聊聊邻接图。邻接图是一种表示图的数据结构，它将每个节点的邻居节点（即与该节点直接相连的节点）组织在一起。简单来说，邻接图就是一种方式，让我们快速知道任意一个节点都和哪些节点相连。🌍
为什么用邻接图？
- 直观表示：邻接图直观地表示了节点之间的关系，让我们一眼就能看出哪些节点是直接相连的。
- 高效查询：在邻接图中，查询任意两个节点之间是否存在边是非常快的。
- 适合树结构：对于树这样的无环图，邻接图可以很好地表示其结构，便于我们进行深度优先搜索（DFS）等操作。
题目解析
题目给出了一个无根带权树，树上有n个节点，每个节点都是一个服务器。还有一个edges数组，告诉我们哪些节点之间有连接以及连接的权重。🌐
关键的来了，我们需要找出所有可以通过某个中间节点c连接的服务器对a和b。但不是随便哪个节点都能当中间人哦，要满足以下条件：
a < b，且a和b都不能是c。- 从
c到a和从c到b的距离都能被signalSpeed整除。 - 从
c到a和从c到b的路径不能有重叠的边。
暴力枚举的可能性
题目提示中n <= 1000，这意味着我们可以考虑使用暴力枚举的策略。因为节点的数量不是非常大，所以对每个节点进行遍历和计算是可行的。
算法思路
我们构建了一个邻接图来存储每个节点的连接信息。然后，通过深度优先搜索（DFS）遍历整棵树，计算每个节点作为中间节点时，能连接的服务器对的数目。🌳
代码实现
在Scala中，我们使用了ArrayBuffer来动态存储每个节点的邻居信息。DFS函数帮助我们递归地计算每个节点的贡献。最后，我们只需要遍历每个节点，累加它作为中间节点时能连接的服务器对数目。
import scala.collection.mutable.ArrayBuffer
object Solution {
def countPairsOfConnectableServers(edges: Array[Array[Int]], signalSpeed: Int): Array[Int] = {
val n = edges.length + 1
val graph = Array.fill(n)(ArrayBuffer[(Int, Int)]())
for (e <- edges) {
graph(e(0)) += ((e(1), e(2)))
graph(e(1)) += ((e(0), e(2)))
}
def dfs(p: Int, root: Int, curr: Int): Int = {
var res = 0
if (curr == 0) {
res += 1
}
for ((v, cost) <- graph(p)) {
if (v != root) {
res += dfs(v, p, (curr + cost) % signalSpeed)
}
}
res
}
val res = new Array[Int](n)
for (i <- 0 until n) {
var pre = 0
for ((v, cost) <- graph(i)) {
val cnt = dfs(v, i, cost % signalSpeed)
res(i) += pre * cnt
pre += cnt
}
}
res
}
}
时间和空间复杂度分析
- 时间复杂度：由于我们对每个节点都执行了DFS，且每个节点的邻居都会被访问一次，时间复杂度为O(N + E)，其中N是节点数，E是边数。在这个特定问题中，E接近N，所以时间复杂度接近O(N^2)。
- 空间复杂度：我们使用了一个大小为N的数组来存储结果，以及一个邻接图，邻接图的空间复杂度取决于树的稠密程度。在最坏的情况下，如果树是完全二叉树，空间复杂度为O(N)。
结果
最终，我们得到了一个数组count，其中count[i]就是通过服务器i可连接的服务器对的数目。
#tag时间
- #LeetCode挑战
- #算法思维
- #编程日常
- #Scala编程
- #树的深度优先搜索
- #邻接图
- #暴力枚举
- #时间空间复杂度
希望我的分享对你有所帮助，如果你有更好的解法或者想法，欢迎在评论区留言讨论哦！我们一起进步，一起加油！🚀🌈
编程路上，我们一起成长，一起探索未知！👩💻🌟
以上就是今天的分享啦，如果你喜欢这样的内容，记得点赞和关注我哦！我们下次见！😘✨
