hdu 4619 Warm up 2（并查集）

借用题解上的话，就是乱搞题。。

题意理解错了，其实是坐标系画错了，人家个坐标系，我给当矩阵画，真好反了。对于题目描述和数据不符的问题，果断相信数据了（这是有前车之鉴的hdu 4612 Warm up，明明有重边，出题人欺骗我们的智商）然后就杯具了。

我是用并查集搞得。

 1 #include<stdio.h>
 2 #include<string.h>
 3 
 4 const int MAXN=105;
 5 
 6 int mp[MAXN][MAXN];
 7 int p[20000];
 8 int vis[20000];
 9 int find(int x)
10 {
11     return p[x]==x?x:p[x]=find(p[x]);
12 }
13 
14 int main()
15 {
16     int n,m,i,j;
17     int x,y;
18     while(scanf("%d%d",&n,&m)!=EOF)
19     {
20         if(!n&&!m)
21             break;
22         memset(mp,0,sizeof(mp));
23         for(i=1;i<=MAXN*MAXN;i++)
24             p[i]=i;
25         for(i=1;i<=n;i++)
26         {
27             scanf("%d%d",&x,&y);
28             p[find(x*MAXN+y)]=find((x+1)*MAXN+y);
29             mp[x][y]=mp[x+1][y]=1;
30         }
31         for(i=n+1;i<=n+m;i++)
32         {
33             scanf("%d%d",&x,&y);
34             p[find(x*MAXN+y)]=find(x*MAXN+y+1);
35             mp[x][y]=mp[x][y+1]=1;
36         }
37         memset(vis,0,sizeof(vis));
38         for(i=0;i<MAXN;i++)
39         {
40             for(j=0;j<MAXN;j++)
41             {
42                 if(mp[i][j]){
43                     vis[find(i*MAXN+j)]++;
44                 }
45             }
46         }
47         int s=0;
48         for(i=0;i<MAXN*MAXN;i++)
49         {
50             if(vis[i])
51                 s+=vis[i]/2;
52         }
53         printf("%d
",s);
54     }
55     return 0;
56 }

View Code