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;
}