首页 > 代码库 > HDU 1325 POJ 1308 Is It A Tree? (并查集)
HDU 1325 POJ 1308 Is It A Tree? (并查集)
这道题就是裸并查集,关键在于对不是树几种的判断
1. 空树是树 2. 森林不是树 3. 无环
或者从入度来看:1,无环;2,除了根,所有的入度为1,根入度为0;3,这个结构只有一个根,不然是森林了。
这道题本来暑假做的POJ 1308 但是HDU没有过。在于空树没有考虑。
用并查集判断有多少个森林注意编号是随机的,不是次序....
/*input:0 01 1 0 01 2 1 2 0 0 1 2 2 3 4 5 0 01 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 0 01 2 2 1 0 0 -1 -1output:Case 1 is a tree.Case 2 is not a tree.Case 3 is not a tree.Case 4 is not a tree.Case 5 is not a tree.Case 6 is not a tree.*/#include<math.h> #include<stdio.h> #include<string.h> #define inf 0x3ffffff #define maxn 10+100000 #define max(a,b) ((a)>(b)?(a):(b)) int N,M,K; int parent[maxn]; int vis[maxn]; int find(int *parent,int k) { if(parent[k]==-1) return k; parent[k]=find(parent,parent[k]); return parent[k]; } int main() { int i,j,again; int e,r,ans,ee,rr,cnt; int nn; memset(parent,-1,sizeof(parent)); memset(vis,0,sizeof(vis)); nn=ans=again=cnt=0; while(1) { if(again) { for(j=0,i=1;i<=nn;i++) { if(vis[i] && parent[i]==-1) j++; if(j>1) {ans=1;break;} } if(nn==0)ans=0; if(ans) printf("Case %d is not a tree.\n",++cnt); else printf("Case %d is a tree.\n",++cnt); ans=again=0; memset(parent,-1,sizeof(parent)); memset(vis,0,sizeof(vis)); } scanf("%d%d",&e,&r); nn=max(nn,max(e,r)); if(e<0 && r<0) break; if(e==0 && r==0 ) {again=1;continue;} vis[r]=vis[e]=1; if(ans==1) continue; ee=find(parent,e); rr=find(parent,r); if(r!=rr || rr==ee) ans=1; parent[rr]=ee; } return 0; }
HDU 1325 POJ 1308 Is It A Tree? (并查集)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。