class060 拓扑排序的扩展技巧【算法】
算法讲解060【必备】拓扑排序的扩展技巧
2023-12-7 22:23:02
code1 P4017 最大食物链计数
// 最大食物链计数
// a -> b，代表a在食物链中被b捕食
// 给定一个有向无环图，返回
// 这个图中从最初级动物到最顶级捕食者的食物链有几条
// 测试链接 : https://www.luogu.com.cn/problem/P4017
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下所有代码，把主类名改成Main，可以直接通过
package class060;
// 最大食物链计数
// a -> b，代表a在食物链中被b捕食
// 给定一个有向无环图，返回
// 这个图中从最初级动物到最顶级捕食者的食物链有几条
// 测试链接 : https://www.luogu.com.cn/problem/P4017
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下所有代码，把主类名改成Main，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
public class Code01_FoodLines {
public static int MAXN = 5001;
public static int MAXM = 500001;
public static int MOD = 80112002;
// 链式前向星建图
public static int[] head = new int[MAXN];
public static int[] next = new int[MAXM];
public static int[] to = new int[MAXM];
public static int cnt;
// 拓扑排序需要的队列
public static int[] queue = new int[MAXN];
// 拓扑排序需要的入度表
public static int[] indegree = new int[MAXN];
// 拓扑排序需要的推送信息
public static int[] lines = new int[MAXN];
public static int n, m;
public static void build(int n) {
cnt = 1;
Arrays.fill(indegree, 0, n + 1, 0);
Arrays.fill(lines, 0, n + 1, 0);
Arrays.fill(head, 0, n + 1, 0);
}
public static void addEdge(int u, int v) {
next[cnt] = head[u];
to[cnt] = v;
head[u] = cnt++;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in = new StreamTokenizer(br);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
while (in.nextToken() != StreamTokenizer.TT_EOF) {
n = (int) in.nval;
in.nextToken();
m = (int) in.nval;
build(n);
for (int i = 0, u, v; i < m; i++) {
in.nextToken();
u = (int) in.nval;
in.nextToken();
v = (int) in.nval;
addEdge(u, v);
indegree[v]++;
}
out.println(ways());
}
out.flush();
out.close();
br.close();
}
public static int ways() {
int l = 0;
int r = 0;
for (int i = 1; i <= n; i++) {
if (indegree[i] == 0) {
queue[r++] = i;
lines[i] = 1;
}
}
int ans = 0;
while (l < r) {
int u = queue[l++];
if (head[u] == 0) {
// 当前的u节点不再有后续邻居了
ans = (ans + lines[u]) % MOD;
} else {
for (int ei = head[u], v; ei > 0; ei = next[ei]) {
// u -> v
v = to[ei];
lines[v] = (lines[v] + lines[u]) % MOD;
if (--indegree[v] == 0) {
queue[r++] = v;
}
}
}
}
return ans;
}
}
code2 851. 喧闹和富有
// 喧闹和富有
// 从 0 到 n - 1 编号，其中每个人都有不同数目的钱，以及不同程度的安静值
// 给你一个数组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] 最小的人）。
// 测试链接 : https://leetcode.cn/problems/loud-and-rich/
package class060;
import java.util.ArrayList;
// 喧闹和富有
// 从 0 到 n - 1 编号，其中每个人都有不同数目的钱，以及不同程度的安静值
// 给你一个数组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] 最小的人）。
// 测试链接 : https://leetcode.cn/problems/loud-and-rich/
public class Code02_LoudAndRich {
public static int[] loudAndRich(int[][] richer, int[] quiet) {
int n = quiet.length;
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
int[] indegree = new int[n];
for (int[] r : richer) {
graph.get(r[0]).add(r[1]);
indegree[r[1]]++;
}
int[] queue = new int[n];
int l = 0;
int r = 0;
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
queue[r++] = i;
}
}
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
ans[i] = i;
}
while (l < r) {
int cur = queue[l++];
for (int next : graph.get(cur)) {
if (quiet[ans[cur]] < quiet[ans[next]] ) {
ans[next] = ans[cur];
}
if (--indegree[next] == 0) {
queue[r++] = next;
}
}
}
return ans;
}
}
code3 2050. 并行课程 III
// 并行课程 III
// 给你一个整数 n ，表示有 n 节课，课程编号从 1 到 n
// 同时给你一个二维整数数组 relations ，
// 其中 relations[j] = [prevCoursej, nextCoursej]
// 表示课程 prevCoursej 必须在课程 nextCoursej 之前 完成（先修课的关系）
// 同时给你一个下标从 0 开始的整数数组 time
// 其中 time[i] 表示完成第 (i+1) 门课程需要花费的 月份 数。
// 请你根据以下规则算出完成所有课程所需要的 最少 月份数：
// 如果一门课的所有先修课都已经完成，你可以在 任意 时间开始这门课程。
// 你可以 同时 上 任意门课程 。请你返回完成所有课程所需要的 最少 月份数。
// 注意：测试数据保证一定可以完成所有课程（也就是先修课的关系构成一个有向无环图）
// 测试链接 : https://leetcode.cn/problems/parallel-courses-iii/
package class060;
import java.util.ArrayList;
// 并行课程 III
// 给你一个整数 n ，表示有 n 节课，课程编号从 1 到 n
// 同时给你一个二维整数数组 relations ，
// 其中 relations[j] = [prevCoursej, nextCoursej]
// 表示课程 prevCoursej 必须在课程 nextCoursej 之前 完成（先修课的关系）
// 同时给你一个下标从 0 开始的整数数组 time
// 其中 time[i] 表示完成第 (i+1) 门课程需要花费的 月份 数。
// 请你根据以下规则算出完成所有课程所需要的 最少 月份数：
// 如果一门课的所有先修课都已经完成，你可以在 任意 时间开始这门课程。
// 你可以 同时 上 任意门课程 。请你返回完成所有课程所需要的 最少 月份数。
// 注意：测试数据保证一定可以完成所有课程（也就是先修课的关系构成一个有向无环图）
// 测试链接 : https://leetcode.cn/problems/parallel-courses-iii/
public class Code03_ParallelCoursesIII {
public static int minimumTime(int n, int[][] relations, int[] time) {
// 点 : 1....n
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
int[] indegree = new int[n + 1];
for (int[] edge : relations) {
graph.get(edge[0]).add(edge[1]);
indegree[edge[1]]++;
}
int[] queue = new int[n];
int l = 0;
int r = 0;
for (int i = 1; i <= n; i++) {
if (indegree[i] == 0) {
queue[r++] = i;
}
}
int[] cost = new int[n + 1];
int ans = 0;
while (l < r) {
int cur = queue[l++];
// 1 : time[0]
// x : time[x-1]
cost[cur] += time[cur - 1];
ans = Math.max(ans, cost[cur]);
for (int next : graph.get(cur)) {
cost[next] = Math.max(cost[next], cost[cur]);
if (--indegree[next] == 0) {
queue[r++] = next;
}
}
}
return ans;
}
}
code4 2127. 参加会议的最多员工数
// 参加会议的最多员工数
// 一个公司准备组织一场会议，邀请名单上有 n 位员工
// 公司准备了一张 圆形 的桌子，可以坐下 任意数目 的员工
// 员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工
// 每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议
// 每位员工喜欢的员工 不会 是他自己。给你一个下标从 0 开始的整数数组 favorite
// 其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目
// 测试链接 : https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting/
package class060;
// 参加会议的最多员工数
// 一个公司准备组织一场会议，邀请名单上有 n 位员工
// 公司准备了一张 圆形 的桌子，可以坐下 任意数目 的员工
// 员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工
// 每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议
// 每位员工喜欢的员工 不会 是他自己。给你一个下标从 0 开始的整数数组 favorite
// 其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目
// 测试链接 : https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting/
public class Code04_MaximumEmployeesToBeInvitedToAMeeting {
public static int maximumInvitations(int[] favorite) {
// 图 : favorite[a] = b : a -> b
int n = favorite.length;
int[] indegree = new int[n];
for (int i = 0; i < n; i++) {
indegree[favorite[i]]++;
}
int[] queue = new int[n];
int l = 0;
int r = 0;
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
queue[r++] = i;
}
}
// deep[i] : 不包括i在内，i之前的最长链的长度
int[] deep = new int[n];
while (l < r) {
int cur = queue[l++];
int next = favorite[cur];
deep[next] = Math.max(deep[next], deep[cur] + 1);
if (--indegree[next] == 0) {
queue[r++] = next;
}
}
// 目前图中的点，不在环上的点，都删除了！ indegree[i] == 0
// 可能性1 : 所有小环(中心个数 == 2)，算上中心点 + 延伸点，总个数
int sumOfSmallRings = 0;
// 可能性2 : 所有大环(中心个数 > 2)，只算中心点，最大环的中心点个数
int bigRings = 0;
for (int i = 0; i < n; i++) {
// 只关心的环！
if (indegree[i] > 0) {
int ringSize = 1;
indegree[i] = 0;
for (int j = favorite[i]; j != i; j = favorite[j]) {
ringSize++;
indegree[j] = 0;
}
if (ringSize == 2) {
sumOfSmallRings += 2 + deep[i] + deep[favorite[i]];
} else {
bigRings = Math.max(bigRings, ringSize);
}
}
}
return Math.max(sumOfSmallRings, bigRings);
}
}
2023-12-8 11:42:29
