LeetCode-547

题目

547. 省份数量

结果

代码

type DisjointSet struct {
	parent []int // actually, it's a hash table
}

func (s *DisjointSet) union(x, y int) {
	if rootX, rootY := s.find(x), s.find(y); rootX == rootY {
		return
	} else {
		s.parent[rootX] = rootY
	}
}

// find the root(representation) node of the given element, by the way, do path compression
func (s *DisjointSet) find(x int) int {
	if x != s.parent[x] {
		s.parent[x] = s.find(s.parent[x])
	}
	return s.parent[x]
}

func findCircleNum(isConnected [][]int) (ans int) {
	s := DisjointSet{}
	size := len(isConnected)
	for i := 0; i < size; i++ {
		s.parent = append(s.parent, i)
	}
	for i := 0; i < size; i++ {
		for j := i + 1; j < size; j++ {
			if isConnected[i][j] == 1 {
				s.union(i, j)
			}
		}
	}
	// only root node is countered
	for k, v := range s.parent {
		if k == v {
			ans++
		}
	}
	return
}