题意给一个 $n(\le 5\times 10^5)$ 点 $m(\le 5\times 10^5)$ 边的有向无环图，求一个拓扑序满足拓扑序的前缀最大值最少/最多。题解最大的情况比较容易想到，从当前能走的点中选编号最小的点即可，用堆维护。至于最小的情况，直接选最大的点拓展会喜提46分。很容易想到这种方法的问题所在，如果很小的一个点连着一个很大的点，把这两个都选了有可能最优。考虑对贪心进行优...
题意定义半连通图为对于 $\forall (u,v)$ ，存在从 $u$ 到 $v$ 或从 $v$ 到 $u$ 的有向路径。给出一个有向图，求最大半连通子图中的节点个数以及最大半连通子图的个数。其中点数 $N\le 100000$ ，边数 $M\le 1000000$ 。题解显然连通图也属于半连通图，那么可以先缩点，记录每个点的新编号 $scc[]$ 以及包含节点个数 $siz[]$ ，并删...