Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
题解(慎入,勿喷)这题先做遍染色染色时记录出度为0的点和入度为0的点各有多少个,取二者最大值即可 证明: 充分性:这个图肯定是有向图半连通,之后一个出度为0的点连一个入度为0的点这样形成环,二者有一方还剩下几个就往环上连就行了 必要性:这些入度为0或出度为0的点你不连它他肯定还是不连通所以至少是max(出度为0的点,入度为0的点} 最后注意下只有一个强连通分量的情况就行 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator