sgu 174 Walls

本文从WordPress迁移而来, 查看全部WordPress迁移文章

map(hash) + 并查集

题意:有n条直线,每一行就是没条直线的两个端点的笛卡尔坐标,保证每条直线都是合法的即不是是一个点,另外保证所有直线不会交叉。依次添加这些直线直到出现一个环为止,输出这条直线的标号

这题其实算是水题,选拔又没做出来。没添加一条直线的时候,其实是讲两个端点连起来了,所以是讲端点可并的过程,如果两个端点之前已经并起来了,再加一条边就成环了,这是个很明显的并查集。不过要解决一个问题就是数据比较大,10^9开不了数组标记哪些点已经出现过,所以可以用hash,或者省事直接用个map就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <utility>
using namespace std;
#define N 200010
#define cl memset
#define pii pair<int ,int>
#define mp make_pair

map<pii,int>m;
int n,tot,res,p[2*N];
int x1[N],y1[N],x2[N],y2[N];

int find(int x){
return x == p[x] ? x : p[x] = find(p[x]);
}

int main(){
while(scanf("%d",&n)!=EOF){
for(int i = 1; i <= n; i++){
scanf("%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i]);
p[i] = i; p[i + n] = i + n;
}
tot = res = 0;
m.clear();
for(int i = 1; i <= n ; i++){
pii a,b;
a = mp(x1[i],y1[i]);
b = mp(x2[i],y2[i]);
if(m[a] == 0) m[a] = ++tot;
if(m[b] == 0) m[b] = ++tot;
int fa = find(m[a]);
int __fa = find(m[b]);
if(fa == __fa){
res = i; break;
}
p[fa] = __fa;
}
printf("%d\n",res);
}
return 0;
}