class060 拓扑排序的扩展技巧【算法】

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;
  }
}

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;
  }
}

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;
  }
}

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);
  }
}