首页 > 可达性
开通博客写题解
头像 回归梦想
发表于 2020-06-22 19:53:03
来源：牛客网 @[toc] 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 给出一个 0 ≤ N ≤ 105 点数、0 ≤ M ≤ 105 边数的有向图，输出一个尽可能小的点集，使得从这些 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 威风镰鼬
发表于 2021-08-31 14:07:15
思路 首先tarjan缩点，保证是一个DAG之后，再输出topo排序的起点就可以了。不过数据是不是放水了，我求出来的强连通分量是按访问顺序定谁是fa的，交上去也是对的。难道不应该是要保证每个scc的fa都是里面编号最小那个点吗？所以我弄了个flag数组意义注释了。莫名其妙就A了希望大佬能帮我解答一下 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 ZZZYM
发表于 2022-02-22 00:19:06
可达性 思路 利用有向图的强连通分量中的tarjan算法进行缩点, 输出缩点后的图中入度为0的结点编号, 缩点后的图中结点编号为该点对应强连通分量中点编号的最小值 代码 #include <bits/stdc++.h> using namespace std; typedef long 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”