codeforces #346 div 2 E. New Reform (和图有关的的计数)

题意:

给出n个点,条边的无向图,无重边,无自环。现在要求把所有的无向边换成有向边,使得入度为0的点最少。问最少的入度为0的点是多少。

思路:

对于每个联通快,如果有环,我们可以顺时针连接环上的点,以指向环的方向连接联通快上的其他点,这样就可以保证所有点的入度都不为0. 如果是树形结构,则不可避免得使得一个点的入度为0.

因此对于有环的联通块答案为0,没环的答案为1.

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz