026 - Independent Set on a Tree（★4）

キーワード

解説

グラフ $G = (V, E)$ であって, $V = V_1 \sqcup V_2$ であって, 任意の $u \in V_1, v \in V_2$ について, $(u, v) \notin E$ であるようなものを二部グラフという. 木は必ず二部グラフとなる.

二部グラフを赤と緑で彩色すると, 少なくとも一方は $N/2$ 個以上存在する.

彩色は深さ優先探索(DFS)か幅優先探索(BFS)を用いて行うことができる.

どちらを用いる場合も, 色を $(0, 1)$ で管理することで, $1 - \text{previousColor}$ で隣り合う頂点を別の色で塗ることができる.

BFS を用いる場合

colors := make([]int, n+1)
for i := 0; i < n+1; i++ {
    colors[i] = -1
}
colors[1] = 0
 
for !q.Empty() {
    v := q.Front()
    q.Pop()
 
    for _, u := range g[v] {
        if colors[u] == -1 {
            colors[u] = 1 - colors[v]
            q.Push(u)
        }
    }
}

DFS を用いる場合

colors := make([]int, n+1)
for i := 1; i < n+1; i++ {
    colors[i] = -1
}
 
var dfs func(v, c int)
dfs = func(v, c int) {
    colors[v] = c
    for _, u := range g[v] {
        if colors[u] == -1 {
            dfs(u, 1-c)
        }
    }
}
 
dfs(1, 0)

提出コード

BFS

func main() {
	var n int
	scanIntVariables(&n)
 
	g := make([][]int, n+1)
	for i := 0; i < n; i++ {
		var a, b int
		scanIntVariables(&a, &b)
 
		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
	}
 
	q := queue.New[int]()
	q.Push(1)
 
	colors := make([]int, n+1)
	for i := 0; i < n+1; i++ {
		colors[i] = -1
	}
	colors[1] = 0
 
	for !q.Empty() {
		v := q.Front()
		q.Pop()
 
		for _, u := range g[v] {
			if colors[u] == -1 {
				colors[u] = 1 - colors[v]
				q.Push(u)
			}
		}
	}
 
	reds := make([]int, 0, n)
	blues := make([]int, 0, n)
	for i := 1; i < n+1; i++ {
		if colors[i] == 0 {
			reds = append(reds, i)
		} else {
			blues = append(blues, i)
		}
	}
 
	if len(reds) >= len(blues) {
		for i := 0; i < n/2; i++ {
			write(reds[i], " ")
		}
	} else {
		for i := 0; i < n/2; i++ {
			write(blues[i], " ")
		}
	}
}

DFS

func main() {
	var n int
	scanIntVariables(&n)
 
	g := make([][]int, n+1)
	for i := 0; i < n; i++ {
		var a, b int
		scanIntVariables(&a, &b)
 
		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
	}
 
	colors := make([]int, n+1)
	for i := 1; i < n+1; i++ {
		colors[i] = -1
	}
 
	var dfs func(v, c int)
	dfs = func(v, c int) {
		colors[v] = c
		for _, u := range g[v] {
			if colors[u] == -1 {
				dfs(u, 1-c)
			}
		}
	}
 
	dfs(1, 0)
 
	reds := make([]int, 0, n)
	blues := make([]int, 0, n)
	for i := 1; i < n+1; i++ {
		if colors[i] == 0 {
			reds = append(reds, i)
		} else {
			blues = append(blues, i)
		}
	}
 
	if len(reds) >= len(blues) {
		for i := 0; i < n/2; i++ {
			write(reds[i], " ")
		}
	} else {
		for i := 0; i < n/2; i++ {
			write(blues[i], " ")
		}
	}
}

022 - Cubic Cake（★2）027 - Sign Up Requests （★2）