本文从WordPress迁移而来, 查看全部WordPress迁移文章
map(hash) + 并查集
题意:有n条直线,每一行就是没条直线的两个端点的笛卡尔坐标,保证每条直线都是合法的即不是是一个点,另外保证所有直线不会交叉。依次添加这些直线直到出现一个环为止,输出这条直线的标号
这题其实算是水题,选拔又没做出来。没添加一条直线的时候,其实是讲两个端点连起来了,所以是讲端点可并的过程,如果两个端点之前已经并起来了,再加一条边就成环了,这是个很明显的并查集。不过要解决一个问题就是数据比较大,10^9开不了数组标记哪些点已经出现过,所以可以用hash,或者省事直接用个map就行了
1 |
|