bnu5472(hdu1272)无向
bnu5525(hdu1325)有向
这两道题有个需要注意的地方，就是它的边是随机出现的，并不是和其他的并查集的题一样，从1-n什么的，所以用一个数组，或者map存放着存在的边，判断一个图是不是为树，如果是无向的话，就是边为点数-1,如果是有向图呢？除了前面一条还要保证的是必须只有一个根，这个道理很简单，如果非联通图的话生成树是一个森林，当然不行，所以必须保证只有一个根。
很多方案，我都不会，转化为并查集的方案：
1.每来一个条边加入到集合中，最后判断，存在的这些点必须只属于一个集合。（有向图在加入边的时候必须一个固定的加入方向，没有按什么树的深度优化并查集的，否则就错了。） 当然有向图如果一个新的节点指向一个有根的孩子节点，那么就一定不是树了。如果两个节点有同一个根，他们又多了一条边。。这个你懂的。
2.void 也是一个棵树，这个退化情况希望大家可以处理到一般情况中，退化情况如果总是单独处理，只能说明你水平不行，退化情况，一定要统一处理，这样才能化繁为简。
代码：
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
const int maxnum=100000+1;
#define re1(i,n) for(int i=1;i<=(n);++i)
int G[maxnum];
int yank[maxnum];
int find(int x){
if(G[x]!=x)
G[x]=find(G[x]);
return G[x];
}
bool u3n(int a,int b){
int x= find(a);
int y= find(b);
if(x==y)
return false;
if(yank[x]>yank[y])
G[y]=x;
else{
G[x]=y;
if(yank[x]==yank[y])
yank[y]++;
}
return true;
}
int main(){
int t1,t2,tcase=0;
while(scanf("%d%d",&t1,&t2)){
if(t1==t2 && t2==-1)
break;
re1(u,maxnum){
G[u]=u;
yank[u]=0;
}
map<int,int> edge;
tcase++;
bool flag=true;
while(!(t1==t2 && t2==0)){
edge[t1]=1;
edge[t2]=1;
if(!u3n(t1,t2))
flag=false;
scanf("%d%d",&t1,&t2);
}
int sum=0;
re1(u,maxnum){
if(edge[u]==1&&G[u]==u)
sum++;
}
if(!(sum==0 || sum==1))
flag=false;
if(flag)
printf("Yes\n");
else
printf("No\n");
}
}
#include<iostream>
#include<cstdio>
using namespace std;
const int maxnum=100000+10;
#define re1(i,n) for(int i=(1);i<=(n);++i)
template<class T>
void show(T *a,int n,int m){
for(int i=n;i<=m;++i)
cout<<a[i]<< ' ';
cout<<endl;
}
int G[maxnum];
int yank[maxnum];
int edge[maxnum];
int find(int x){
if(G[x]!=x)
G[x]=find(G[x]);
return G[x];
}
bool u3n(int a,int b){
int x= find(a);
int y= find(b);
if(x==y)
return false;
G[y]=x;
return true;
}
int main(){
//#define home gggin
#ifdef home
freopen("6.txt","r",stdin);
#endif
int t1,t2,tcase=0;
while(scanf("%d%d",&t1,&t2)){
if(t1<0 || t2<0)
break;
re1(u,maxnum-1){
G[u]=u;
edge[u]=0;
}
tcase++;
bool flag=true;
while(!(t1==t2 && t2==0)){
edge[t1]=1;
edge[t2]=1;
if(find(t2)!=t2)
flag=false;
else if(!u3n(t1,t2))
flag=false;
scanf("%d%d",&t1,&t2);
}
//show(G,1,5);
int sum=0;
re1(u,maxnum-1){
if(edge[u]&&G[u]==u)
sum++;
}
if(!(sum==0 || sum==1))
flag=false;
if(flag)
printf("Case %d is a tree.\n",tcase);
else
printf("Case %d is not a tree.\n",tcase);
}
}
posted on 2012-12-10 21:50
Gin 阅读(8023)
评论(2) 编辑 收藏 引用 所属分类:
Data Structure