leetcode-go/leetcode/medium/547.friend-circles.go

func findCircleNum(M [][]int) int {
	n := len(M)
	if n == 0 {
		return 0
	}
	adj := make([][]int, n) // Much faster than the matrix M
	for i := 0; i < n; i++ {
		for j := i; j < n; j++ {
			if M[i][j] == 1 {
				adj[i] = append(adj[i], j)
				if i != j {
					adj[j] = append(adj[j], i)
				}
			}
		}
	}
	visited := make([]bool, n)
	cnt := 0
	for i := range adj {
		if !visited[i] && len(adj[i]) != 0 {
			dfs(adj, &visited, i)
			cnt++
		}
	}
	return cnt
}

func dfs(adj [][]int, visited *[]bool, i int) {
	(*visited)[i] = true
	for _, v := range adj[i] {
		if !(*visited)[v] {
			dfs(adj, visited, v)
		}
	}
}