042.拓扑排序的扩展技巧

前置知识：同余原理、拓扑排序

拓扑排序的扩展技巧 §

本节课继续讲解拓扑排序的题目

重要技巧：利用拓扑排序的过程，上游节点逐渐推送消息给下游节点的技巧

备注 §

这个技巧已经是树型 dp 的内容了，不过即便不会动态规划，本节课也能听懂

动态规划专题（包括树型 dp）会在后续【必备】课程里讲述

题目1.最大食物链计数 §

题目描述 §

给你一个食物网，你要求出这个食物网中最大食物链的数量。

（这里的“最大食物链”，指的是生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。）

由于这个结果可能过大，你只需要输出总数模上 80112002 的结果。

测试链接 §

P4017 最大食物链计数

答案 §

package main
 
import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)
 
const (
	MAXN = 5001
	MAXM = 500001
	MOD  = 80112002
)
 
var (
	n int
	m int
	// 链式前向星
	head     = [MAXN]int{}
	next     = [MAXM]int{}
	to       = [MAXM]int{}
	cnt      = 1
	inDegree = [MAXN]int{}
	queue    = [MAXN]int{}
	h, t     = 0, 0
	count    = [MAXN]int{}
)
 
func build() {
	cnt = 1
	for i := 1; i <= n; i++ {
		head[i] = 0
		inDegree[i] = 0
		count[i] = 0
	}
}
 
func addEdge(f, t int) {
	next[cnt] = head[f]
	to[cnt] = t
	head[f] = cnt
	cnt++
}
 
func topoSort() int {
	h, t = 0, 0
	for i := 1; i <= n; i++ {
		if inDegree[i] == 0 {
			count[i] = 1
			queue[t] = i
			t++
		}
	}
	ans := 0
	for h < t {
		cur := queue[h]
		h++
		if head[cur] == 0 {
			// 最顶级消费者
			ans = (ans + count[cur]) % MOD
		} else {
			for i := head[cur]; i > 0; i = next[i] {
				inDegree[to[i]]--
				if inDegree[to[i]] == 0 {
					queue[t] = to[i]
					t++
				}
				count[to[i]] = (count[to[i]] + count[cur]) % MOD
			}
		}
	}
	return ans
}
 
func main() {
	in := bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for in.Scan() {
		n, _ = strconv.Atoi(in.Text())
		in.Scan()
		m, _ = strconv.Atoi(in.Text())
		build()
		from, to := 0, 0
		for i := 0; i < m; i++ {
			in.Scan()
			from, _ = strconv.Atoi(in.Text())
			in.Scan()
			to, _ = strconv.Atoi(in.Text())
			addEdge(from, to)
			inDegree[to]++
		}
		fmt.Fprintln(out, topoSort())
	}
	out.Flush()
}

题目2.喧闹和富有 §

题目描述 §

有一组 n 个人作为实验对象，从 0 到 n - 1 编号，其中每个人都有不同数目的钱，以及不同程度的安静值（quietness）。为了方便起见，我们将编号为 x 的人简称为 “person x “。

给你一个数组 richer ，其中 richer[i] = [ai, bi] 表示 person ai 比 person bi 更有钱。另给你一个整数数组 quiet ，其中 quiet[i] 是 person i 的安静值。richer 中所给出的数据 逻辑自洽（也就是说，在 person x 比 person y 更有钱的同时，不会出现 person y 比 person x 更有钱的情况 ）。

现在，返回一个整数数组 answer 作为答案，其中 answer[x] = y 的前提是，在所有拥有的钱肯定不少于 person x 的人中，person y 是最安静的人（也就是安静值 quiet[y] 最小的人）。

提示：

• n == quiet.length
• 1 <= n <= 500
• 0 <= quiet[i] < n
• quiet 的所有值 互不相同
• 0 <= richer.length <= n * (n - 1) / 2
• 0 <= ai, bi < n
• ai != bi
• richer 中的所有数对 互不相同
• 对 richer 的观察在逻辑上是一致的

测试链接 §

851.喧闹和富有

答案 §

func loudAndRich(richer [][]int, quiet []int) []int {
	n := len(quiet)
	ans := make([]int, n)
	inDegree := make([]int, n)
	graph := make([][]int, n)
	for i := range graph {
		ans[i] = i // 默认是自己
		graph[i] = []int{}
	}
	for _, v := range richer {
		graph[v[0]] = append(graph[v[0]], v[1])
		inDegree[v[1]]++
	}
	queue := make([]int, n)
	head, tail := 0, 0
	for i, v := range inDegree {
		if v == 0 {
			queue[tail] = i
			tail++
		}
	}
	for head < tail {
		cur := queue[head]
		head++
		for _, next := range graph[cur] {
			inDegree[next]--
			if inDegree[next] == 0 {
				queue[tail] = next
				tail++
			}
			if quiet[ans[cur]] < quiet[ans[next]] {
				ans[next] = ans[cur]
			}
		}
	}
	return ans
}

题目3.并行课程 III §

题目描述 §

给你一个整数 n ，表示有 n 节课，课程编号从 1 到 n 。同时给你一个二维整数数组 relations ，其中 relations[j] = [prevCoursej, nextCoursej] ，表示课程 prevCoursej 必须在课程 nextCoursej 之前 完成（先修课的关系）。同时给你一个下标从 0 开始的整数数组 time ，其中 time[i] 表示完成第 (i+1) 门课程需要花费的 月份 数。

请你根据以下规则算出完成所有课程所需要的 最少 月份数：

• 如果一门课的所有先修课都已经完成，你可以在 任意 时间开始这门课程。
• 你可以 同时 上 任意门课程 。

请你返回完成所有课程所需要的 最少 月份数。

注意：测试数据保证一定可以完成所有课程（也就是先修课的关系构成一个有向无环图）。

测试链接 §

2050.并行课程 III

答案 §

func minimumTime(n int, relations [][]int, time []int) int {
	graph := make([][]int, n+1)
	inDegree := make([]int, n+1)
	for i := range graph {
		graph[i] = []int{}
	}
	for _, v := range relations {
		graph[v[0]] = append(graph[v[0]], v[1])
		inDegree[v[1]]++
	}
	queue := make([]int, n)
	head, tail := 0, 0
	for i := 1; i <= n; i++ {
		if inDegree[i] == 0 {
			queue[tail] = i
			tail++
		}
	}
	ans := 0
	cost := make([]int, n+1)
	for head < tail {
		cur := queue[head]
		head++
		cost[cur] += time[cur-1]
		if len(graph[cur]) == 0 {
			ans = max(ans, cost[cur])
		} else {
			for _, next := range graph[cur] {
				inDegree[next]--
				if inDegree[next] == 0 {
					queue[tail] = next
					tail++
				}
				cost[next] = max(cost[next], cost[cur])
			}
		}
	}
	return ans
}

题目4.参加会议的最多员工数 §

题目描述 §

一个公司准备组织一场会议，邀请名单上有 n 位员工。公司准备了一张 圆形 的桌子，可以坐下 任意数目 的员工。

员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工，每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议。每位员工喜欢的员工 不会 是他自己。

给你一个下标从 0 开始的整数数组 favorite ，其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目 。

提示：

• n == favorite.length
• 2 <= n <= 10^5
• 0 <= favorite[i] <= n - 1
• favorite[i] != i

测试链接 §

2127.参加会议的最多员工数

思路 §

两种情况可以最多员工数：

1. 所有小环（中心个数 == 2），算上中心点 + 延伸点，总个数
2. 所有大环（中心个数 > 2），只算中心点，最大环的中心点个数

答案 §

func maximumInvitations(favorite []int) int {
	// 图已经有了，favorite[a] = b: a -> b
	n := len(favorite)
	inDegree := make([]int, n)
	for i := 0; i < n; i++ {
		inDegree[favorite[i]]++
	}
	queue := make([]int, n)
	head, tail := 0, 0
	for i, degree := range inDegree {
		if degree == 0 {
			queue[tail] = i
			tail++
		}
	}
	// deep[i]: 不包括 i 在内，i 之前的最长链的长度
	deep := make([]int, n)
	for head < tail {
		cur := queue[head]
		head++
		next := favorite[cur]
		inDegree[next]--
		if inDegree[next] == 0 {
			queue[tail] = next
			tail++
		}
		deep[next] = max(deep[next], deep[cur]+1)
	}
	// 目前图中的点，不在环上的点，都删除了！ inDegree[i] == 0
 
	// 可能性 1: 所有小环（中心个数 == 2），算上中心点 + 延伸点，总个数
	sumOfSmallRings := 0
	// 可能性 2: 所有大环（中心个数 > 2），只算中心点，最大环的中心点个数
	bigRings := 0
	for i := 0; i < n; i++ {
		if inDegree[i] == 0 {
			// 只关心的环！
			continue
		}
		inDegree[i] = 0
		ringSize := 1
		// 绕环一圈
		for j := favorite[i]; j != i; j = favorite[j] {
			ringSize++
			inDegree[j] = 0
		}
		if ringSize == 2 {
			sumOfSmallRings += 2 + deep[i] + deep[favorite[i]]
		} else {
			bigRings = max(bigRings, ringSize)
		}
	}
	return max(sumOfSmallRings, bigRings)
}