题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3761
题目大意：给定n个位置的小球，小球的运动方向只能是水平或者竖直的。按一定方向推动某球，当行径上有其他球时，停留在被撞球的位置，被撞的球沿原小球运动方向运动，当行径路径上没有其他球时，该小球被剔除。问：只能通过小球的相撞来剔除小球，最少能留下几个小球。
解题思路：首先，可以用并查集找出互相连通的小球集合个数。因为每一次推动的结果可以看成是被推动的小球被剔除了，其他位置上的小球不动，所以可以从每个集合中任选一个小球作DFS。选择推动小球的方向即为该球指向其父亲节点的方向。
1 #include<cmath> 2 #include<cstdio> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 int set[2005]; 8 int e,first[2005],next[4010],v[4010]; 9 bool vis[2005]; 10 struct node 11 { 12 int x,y,l,id; 13 }p[2005],q[2005]; 14 bool cmp1(node a,node b) 15 { 16 if(a.x==b.x) 17 return a.y<b.y; 18 return a.x<b.x; 19 } 20 bool cmp2(node a,node b) 21 { 22 if(a.y==b.y) 23 return a.x<b.x; 24 return a.y<b.y; 25 } 26 void link(int a,int b) 27 { 28 v[e]=b; 29 next[e]=first[a]; 30 first[a]=e++; 31 } 32 int find(int x) 33 { 34 if(set[x]==x) 35 return x; 36 else return set[x]=find(set[x]); 37 } 38 void UN(int a,int b) 39 { 40 int aa,bb; 41 aa=find(a); 42 bb=find(b); 43 if(aa==bb) 44 return; 45 else 46 set[aa]=set[bb]; 47 } 48 void solve(int now) 49 { 50 int k; 51 for(int i=first[now];i!=-1;i=next[i]) 52 { 53 k=v[i]; 54 if(!vis[k]) 55 { 56 vis[k]=true; 57 if(q[now].x==q[k].x) 58 { 59 if(q[now].y>q[k].y)//up 60 q[k].l=1; 61 else 62 q[k].l=2;//down 63 } 64 else 65 { 66 if(q[now].x>q[k].x)//right 67 q[k].l=3; 68 else 69 q[k].l=4;//left; 70 } 71 solve(k); 72 } 73 } 74 if(q[now].l==4) 75 printf("(%d, %d) LEFT ",q[now].x,q[now].y); 76 else if(q[now].l==3) 77 printf("(%d, %d) RIGHT ",q[now].x,q[now].y); 78 else if(q[now].l==1) 79 printf("(%d, %d) UP ",q[now].x,q[now].y); 80 else if(q[now].l==2) 81 printf("(%d, %d) DOWN ",q[now].x,q[now].y); 82 return; 83 } 84 85 86 int main() 87 { 88 int n,j,i,lef[2001],ans; 89 while(~scanf("%d",&n)) 90 { 91 memset(first,-1,sizeof(first)); 92 memset(vis,false,sizeof(vis)); 93 e=0;ans=0; 94 for(i=0;i<n;i++) 95 { 96 p[i].id=i; 97 scanf("%d%d",&p[i].x,&p[i].y); 98 q[i].x=p[i].x;q[i].y=p[i].y; 99 q[i].l=-1; 100 } 101 for(i=0;i<n;i++) 102 set[i]=i; 103 sort(p,p+n,cmp1);//按x从小到大排序 104 for(i=1;i<n;i++) 105 { 106 if(p[i].x==p[i-1].x) 107 { 108 link(p[i].id,p[i-1].id); 109 link(p[i-1].id,p[i].id); 110 UN(p[i].id,p[i-1].id); 111 } 112 } 113 sort(p,p+n,cmp2); 114 for(i=1;i<n;i++) 115 { 116 if(p[i].y==p[i-1].y) 117 { 118 link(p[i].id,p[i-1].id); 119 link(p[i-1].id,p[i].id); 120 UN(p[i].id,p[i-1].id); 121 } 122 } 123 for(i=0;i<n;i++) 124 { 125 if(set[i]==i) 126 lef[ans++]=i; 127 } 128 cout<<ans<<endl; 129 for(i=0;i<ans;i++) 130 { 131 vis[lef[i]]=true; 132 solve(lef[i]); 133 } 134 // cout<<e<<endl; 135 } 136 137 return 0; 138 }