首页
Python
Java
前端
数据库
Linux
Chatgpt专题
开发者工具箱
4235专题
DTOJ #4235. 交朋友
题意: 给定一个n个点m条边的有向图,对于同一个点连向的两个点可以互相连双向边,求图中最多有几条边。 题解: 直观地想,首先对于每一个点,若它的出度大于1,则它连向的边为一个完全图,但每个点做完后又会产生影响,因此没法保证效率。 发现“对于同一个点连向的两个点可以互相连双向边”这个条件类似于并查集,即把双向边视为无向边,这样恰好满足了并查集的性质。 因为原始的边不在并查集的考虑范围内,故用原始的边
阅读更多...