本文主要是介绍DTOJ #4235. 交朋友，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给定一个n个点m条边的有向图，对于同一个点连向的两个点可以互相连双向边，求图中最多有几条边。
题解：
直观地想，首先对于每一个点，若它的出度大于1，则它连向的边为一个完全图，但每个点做完后又会产生影响，因此没法保证效率。
发现“对于同一个点连向的两个点可以互相连双向边”这个条件类似于并查集，即把双向边视为无向边，这样恰好满足了并查集的性质。
因为原始的边不在并查集的考虑范围内，故用原始的边去连这个并查集，得到的就是一些完全图（集合）和一些有向边，就很好算了。先用出度大于1的每个点的去连，然后考虑一条原始有向边的贡献，那也只可能是将它的起点、终点连起来了，发现条件为起点有另外的出边，即起点的集合大小大于1。因为对于边不好按一定顺序访问，故考虑访问点，因为只有所在集合大小大于1的点有用，且每个点最多只会有变得有用一次、用一次，故bfs一下，每次用有用的点去连，再将变得有用的点入队列即可。
这篇关于DTOJ #4235. 交朋友的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
