题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3761
题目大意：给定n个位置的小球，小球的运动方向只能是水平或者竖直的。按一定方向推动某球，当行径上有其他球时，停留在被撞球的位置，被撞的球沿原小球运动方向运动，当行径路径上没有其他球时，该小球被剔除。问：只能通过小球的相撞来剔除小球，最少能留下几个小球。
解题思路：首先，可以用并查集找出互相连通的小球集合个数。因为每一次推动的结果可以看成是被推动的小球被剔除了，其他位置上的小球不动，所以可以从每个集合中任选一个小球作DFS。选择推动小球的方向即为该球指向其父亲节点的方向。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int set[];
int e,first[],next[],v[];
bool vis[];
struct node
{
int x,y,l,id;
}p[],q[];
bool cmp1(node a,node b)
{
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
bool cmp2(node a,node b)
{
if(a.y==b.y)
return a.x<b.x;
return a.y<b.y;
}
void link(int a,int b)
{
v[e]=b;
next[e]=first[a];
first[a]=e++;
}
int find(int x)
{
if(set[x]==x)
return x;
else return set[x]=find(set[x]);
}
void UN(int a,int b)
{
int aa,bb;
aa=find(a);
bb=find(b);
if(aa==bb)
return;
else
set[aa]=set[bb];
}
void solve(int now)
{
int k;
for(int i=first[now];i!=-;i=next[i])
{
k=v[i];
if(!vis[k])
{
vis[k]=true;
if(q[now].x==q[k].x)
{
if(q[now].y>q[k].y)//up
q[k].l=;
else
q[k].l=;//down
}
else
{
if(q[now].x>q[k].x)//right
q[k].l=;
else
q[k].l=;//left;
}
solve(k);
}
}
if(q[now].l==)
printf("(%d, %d) LEFT\n",q[now].x,q[now].y);
else if(q[now].l==)
printf("(%d, %d) RIGHT\n",q[now].x,q[now].y);
else if(q[now].l==)
printf("(%d, %d) UP\n",q[now].x,q[now].y);
else if(q[now].l==)
printf("(%d, %d) DOWN\n",q[now].x,q[now].y);
return;
} int main()
{
int n,j,i,lef[],ans;
while(~scanf("%d",&n))
{
memset(first,-,sizeof(first));
memset(vis,false,sizeof(vis));
e=;ans=;
for(i=;i<n;i++)
{
p[i].id=i;
scanf("%d%d",&p[i].x,&p[i].y);
q[i].x=p[i].x;q[i].y=p[i].y;
q[i].l=-;
}
for(i=;i<n;i++)
set[i]=i;
sort(p,p+n,cmp1);//按x从小到大排序
for(i=;i<n;i++)
{
if(p[i].x==p[i-].x)
{
link(p[i].id,p[i-].id);
link(p[i-].id,p[i].id);
UN(p[i].id,p[i-].id);
}
}
sort(p,p+n,cmp2);
for(i=;i<n;i++)
{
if(p[i].y==p[i-].y)
{
link(p[i].id,p[i-].id);
link(p[i-].id,p[i].id);
UN(p[i].id,p[i-].id);
}
}
for(i=;i<n;i++)
{
if(set[i]==i)
lef[ans++]=i;
}
cout<<ans<<endl;
for(i=;i<ans;i++)
{
vis[lef[i]]=true;
solve(lef[i]);
}
// cout<<e<<endl;
} return ;
}