[LeetCode]Sentence Similarity II

这道题和Sentence Similarity是类似的，唯一的区别是similarity是传递的。所以这道题我们要建图，然后找所有的connected component，这里有两种方法，第一种是dfs，时间空间复杂度均为O(N + M)，N为节点数，M为边数，代码如下：



Union Find也可以用来解决图的连接性的问题，具体可以参考链接的文章。时间空间复杂度均为O(N + M)，N为节点数，M为边数，代码如下：