2018计蒜之道复赛D题

未分类

题意：
给定$m$个单向的关系$(u,v)$,表示$u$能到达$v$,需要构造一个图满足这些条件,问最少需要多少条边?

题解：
首先我们只需要分别考虑其中的弱联通子图（把单向边看成无向边的联通子图），不同的弱联通子图互不影响。
一个$n$个点的弱联通子图，如果其中存在环，则至少需要$n$条边才能满足条件（每个点都需要有一个入边），如果其中不存在环，则最少需要$n-1$条（少于$n-1$条边时图不能（弱）联通）.
可以证明在有环的有向图中，只要依次用有向边连接$i$和$i+1(i<n)$，$n$和$1$即可.易证这种连接会生成一个强连通图,此时只要$n$条边.
在无环的无向图$(DAG)$中，可知存在拓扑排序，假设一个合法的拓扑排序是$k_1,k_2,...,k_n$，那么只需要依次连接$k_i$和$k_{i+1}(i<n)$即可，这样只需要$n-1$条边.
综上可以得出结论：
将原图分成若干个弱联通子图，对某一个有$V$个点的弱联通子图，如果该图中存在有向环则$ans+=V$，否则$ans+=V-1$.
时间复杂度$O(N+M)$