网站iis7.5配置,网页传奇大全,重庆市建设工程信息网招标文件,自媒体135的网站是多少打卡记录 参加会议的最多员工数#xff08;拓扑排序 分类讨论#xff09;
链接
计算内向基环树的最大基环#xff0c;基环树基环为2的情况分类讨论。
class Solution {
public:int maximumInvitations(vectorint favorite) {int n favorite.size();vector…打卡记录 参加会议的最多员工数拓扑排序 分类讨论
链接
计算内向基环树的最大基环基环树基环为2的情况分类讨论。
class Solution {
public:int maximumInvitations(vectorint favorite) {int n favorite.size();vectorint deg(n);for (int f: favorite) {deg[f]; // 统计基环树每个节点的入度}vectorvectorint rg(n); // 反图queueint q;for (int i 0; i n; i) {if (deg[i] 0) {q.push(i);}}while (!q.empty()) { // 拓扑排序剪掉图上所有树枝int x q.front();q.pop();int y favorite[x]; // x 只有一条出边rg[y].push_back(x);if (--deg[y] 0) {q.push(y);}}// 通过反图 rg 寻找树枝上最深的链functionint(int) rdfs [](int x) - int {int max_depth 1;for (int son: rg[x]) {max_depth max(max_depth, rdfs(son) 1);}return max_depth;};int max_ring_size 0, sum_chain_size 0;for (int i 0; i n; i) {if (deg[i] 0) continue;// 遍历基环上的点deg[i] 0; // 将基环上的点的入度标记为 0避免重复访问int ring_size 1; // 基环长度for (int x favorite[i]; x ! i; x favorite[x]) {deg[x] 0; // 将基环上的点的入度标记为 0避免重复访问ring_size;}if (ring_size 2) { // 基环长度为 2sum_chain_size rdfs(i) rdfs(favorite[i]); // 累加两条最长链的长度} else {max_ring_size max(max_ring_size, ring_size); // 取所有基环长度的最大值}}return max(max_ring_size, sum_chain_size);}
};
