[CF#286 Div2 D]Mr. Kitayuta's Technology(结论题)

时间:2023-01-22 12:32:44

题目:http://codeforces.com/contest/505/problem/D

题目大意:就是给你一个n个点的图,然后你要在图中加入尽量少的有向边,满足所有要求(x,y),即从x可以走到y

分析:

对于输入的图中,可以发现每个连通块是独立的,中间不用连边就可以,于是考虑单个连通块。

如果某个连通块一共有m个点,那么我们知道,我们至少是要加m-1条边才可以保证形成的图是连通的,但是因为是有向边,所以最后形成的图一定是DAG图,这也就意味着这必须要求对于这个连通块,原图也是DAG图,即原图中此连通块内不能有环。

那如果有环怎么办?很显然m-1是不行的,那么最小的办法是什么呢?事实上,只要m条边就行了,那就是把m个点全部串成一串,它们就两两可到了,而且m也一定是最小的

所以方法就是:

1、把每条边当作无向图找连通块

2、对于每个连通块分别处理,尝试拓扑排序,如果结束后仍有点没有进入队列中,则必存在环,ans+=m;如果拓扑排序成功,则必为DAG图,ans+=m-1