算法基础-二分图

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

func isBipartite(graph [][]int) bool {
	n := len(graph)
	visited := make([]bool, n)
	color := make([]bool, n)
	valid := true

	var bfs func(int)
	bfs = func(root int) {
		visited[root] = true
		queue := []int{root}
		for len(queue) > 0 {
			node := queue[0]
			queue = queue[1:]
			for _, next := range graph[node] {
				if !visited[next] {
					color[next] = !color[node]
					visited[next] = true
					queue = append(queue, next)
				} else {
					if color[next] == color[node] {
						valid = false
						return
					}
				}
			}
		}
	}

	for i := 0; i < n; i++ {
		if !visited[i] && valid {
			bfs(i)
		}
	}

	return valid
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

func possibleBipartition(n int, dislikes [][]int) bool {
	graph := make([][]int, n)
	for _, dislike := range dislikes {
		a, b := dislike[0]-1, dislike[1]-1
		graph[a] = append(graph[a], b)
		graph[b] = append(graph[b], a)
	}

	valid := true
	visited := make([]bool, n)
	color := make([]bool, n)
	var dfs func(node int)
	dfs = func(node int) {
		if !valid {
			return
		}
		visited[node] = true
		for _, next := range graph[node] {
			if !visited[next] {
				color[next] = !color[node]
				dfs(next)
			} else {
				if color[next] == color[node] {
					valid = false
					return
				}
			}
		}
	}

	for i := 0; i < n; i++ {
		if !visited[i] && valid {
			dfs(i)
		}
	}
	return valid
}