链接

一、题目描述

给定链表头结点 head，该链表上的每个结点都有一个 唯一的整型值 。同时给定列表 nums，该列表是上述链表中整型值的一个子集。

返回列表 nums 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 nums 中）构成的集合。

示例 1：

输入: head = [0,1,2,3], nums = [0,1,3]
输出: 2
解释: 链表中,0 和 1 是相连接的，且 nums 中不包含 2，所以 [0, 1] 是 nums 的一个组件，同理 [3] 也是一个组件，故返回 2。

示例 2：

输入: head = [0,1,2,3,4], nums = [0,3,1,4]
输出: 2
解释: 链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4] 是两个组件，故返回 2。

提示：

• 链表中节点数为n

• 1 <= n <= 104

• 0 <= Node.val < n

• Node.val 中所有值 不同

• 1 <= nums.length <= n

• 0 <= nums[i] < n

• nums 中所有值 不同

二、实现

按秩合并的并查集

type UnionFind struct {
	parent map[int]int
	rank   map[int]int
}

func NewUnionFind(nums []int) UnionFind {
	uf := UnionFind{
		parent: map[int]int{},
		rank:   map[int]int{},
	}
	for _, v := range nums {
		uf.parent[v] = v
		uf.rank[v] = 1
	}
	return uf
}

func (uf UnionFind) Find(v int) int {
	if uf.parent[v] != v {
		uf.parent[v] = uf.Find(uf.parent[v])
	}
	return uf.parent[v]
}

func (uf UnionFind) Union(x, y int) {
	rootx, rooty := uf.Find(x), uf.Find(y)
	if rootx == rooty {
		return
	}
	if uf.rank[rootx] <= uf.rank[rooty] {
		uf.parent[rootx] = rooty
		uf.rank[rooty] += uf.rank[rootx]
	} else {
		uf.parent[rooty] = rootx
		uf.rank[rootx] += uf.rank[rooty]
	}
}

func numComponents(head *ListNode, nums []int) int {
	// 建表
	exists := [10_001]bool{}
	for _, num := range nums {
		exists[num] = true
	}
	// 并查集，统计合并组件
	uf := NewUnionFind(nums)
	pre := -1
	for ; head != nil; head = head.Next {
		if !exists[head.Val] {
			pre = -1
			continue
		}
		if pre != -1 {
			uf.Union(head.Val, pre)
		}
		pre = head.Val
	}
	// 基于并查集和hashset，统计组件个数
	hashSet := map[int]struct{}{}
	for _, v := range nums {
		hashSet[uf.Find(v)] = struct{}{}
	}
	return len(hashSet)
}