题目的意思是桌子上有几个小球,要求互相碰撞使得最后剩下的小球最少。
当两个小球横坐标或者纵坐标相等时,两个小球可以互相碰撞,如果一个小球前面没有小球的话, 它就会跑到无限远的地方。可以把能够碰撞的小球放到一个集合里面,最终的集合的数量就是剩下的小球的数量。
求集合的方法是用并查集,求最后路径的方法是用树的后根便利。
并查集是一种处理不同集合的数据结构。用一种树形的结构,将每棵树当做一个集合,每棵树的根就是这个树的代表元素,当比较两个元素是否属于一个集合时,只需比较两个元素所在树的根节点是否相同。并查集在合并两个集合的时候,通过修改每个元素的祖先来降低复杂度。比如现在有一颗树是A<- B <- C,即A是树根,C是叶子节点,那么在查询C的代表的时候,顺便将C的父亲节点有B改到A。这样,以后再查询的时候,C只需一次就可以找到它的代表元素。
然后在输出路径的时候,首先构建一个邻接表,每个小球与可以跟他碰撞的小球都会有一个路径。这样,就构成了一个无向图。以没有父节点的节点为根开始深度优先遍历,就可以得到正确的路径。
代码如下(这个代码是参考网上的代码以后自己写的):
#include<iostream>
#include<cstring>
using namespace std;
int x[2005];
int y[2005];
int p[2005];
int visit[2005];
int V[2005][2005];
int n;
int find(int t){
int tmp=t;
while(p[t]!=t){
t=p[t];
}
p[tmp]=t;
return t;
}
void push(int xx,int par){
// cout<<xx<<' '<<par<<endl;
cout<<'('<<x[xx]<<", "<<y[xx]<<')'<<' ';
if(y[xx]==y[par]){
if(x[xx]<x[par])cout<<"RIGHT"<<endl;
else cout<<"LEFT"<<endl;
}
else{
if(y[xx]<y[par])cout<<"UP"<<endl;
else cout<<"DOWN"<<endl;
}
}
void dfs(int xx,int par){
visit[xx]=1;
for(int i=0;i<n;++i){
if(V[xx][i]&&!visit[i]){
dfs(i,xx);
}
}
if(par!=-1){
push(xx,par);
}
}
int main(){
ios::sync_with_stdio(false);
// freopen("data.txt","r",stdin);
while(cin>>n){
int cnt=n;
for(int i=0;i<n;++i){
p[i]=i;
}
memset(V,0,sizeof(V));
memset(visit,0,sizeof(visit));
for(int i=0;i<n;++i){
cin>>x[i]>>y[i];
int a=i;
for(int t=0;t<i;++t){
if(x[t]==x[i]||y[t]==y[i]){
V[i][t]=1;
V[t][i]=1;
int tmp=find(t);
if(p[tmp]!=a){
cnt--;
p[tmp]=a;
}
}
}
}
cout<<cnt<<endl;
for(int i=0;i<n;++i){
if(p[i]==i&&!visit[i]){
dfs(i,-1);
}
}
}
return 0;
}
int find(int t){
int tmp=t;
while(p[t]!=t){
t=p[t];
}
// p[tmp]=t;
return t;
}
int find(int t){
if(p[t]!=t){
p[t]=find(p[t]);
}
return p[t];
}