UF.h (初始化,查找,合并接口）
1 void UFinit(int); 2 //int UFfind(int, int); 3 int UFunion(int, int); 4 int UFnum(int, int);
UF.c (接口实现)
1 #include<stdlib.h> 2 #include "UF.h" 3 4 typedef struct 5 { 6 int *id,*sz; 7 }id_sz; 8 static id_sz ID; 9 void UFinit(int N) 10 { 11 ID.id=malloc(N*sizeof(int)); 12 ID.sz=malloc(N*sizeof(int)); 13 for(int i=0; i<N; i++) 14 { 15 ID.id[i]=i; 16 ID.sz[i]=1; 17 } 18 } 19 static int find(int x) 20 { 21 while(x!=ID.id[x]) 22 { 23 ID.id[x]=ID.id[ID.id[x]]; 24 x=ID.id[x]; 25 } 26 return x; 27 } 28 29 /* 30 int UFfind(int p, int q) 31 { 32 return (find(p)==find(q)); 33 } 34 35 void UFunion(int p, int q) 36 { 37 int i=find(p),j=find(q); 38 if(i==j) return; 39 if(sz[i]<sz[j]) 40 { 41 id[i]=j; 42 sz[j]+=sz[i]; 43 } 44 else 45 { 46 id[j]=i; 47 sz[i]+=sz[j]; 48 } 49 }*/ 50 int UFunion(int p, int q) 51 { 52 int i=find(p),j=find(q); 53 if(i==j) return 0; 54 if(ID.sz[i]<ID.sz[j]) 55 { 56 ID.id[i]=j; 57 ID.sz[j]+=ID.sz[i]; 58 } 59 else 60 { 61 ID.id[j]=i; 62 ID.sz[i]+=ID.sz[j]; 63 } 64 return 1; 65 } 66 67 int UFnum(int p, int N) 68 { 69 int k=N-1,i=k,num=0; 70 71 //while(p!=id[p]) 72 //p=id[p]; 73 p=find(p); 74 while(k>=0) 75 { 76 //while(i!=id[i]) 77 //i=id[i]; 78 i=find(i); 79 if(p==i)num++; 80 i=--k; 81 } 82 return num--; 83 }
main.c (主程序)
1 #include <stdio.h> 2 #include "UF.h" 3 4 int main(void) 5 { 6 int p,q,N; 7 8 scanf("%d",&N); 9 getchar(); 10 11 UFinit(N); 12 /* while(scanf("%d %d", &p, &q)==2) 13 if(!UFfind(p, q)) 14 { 15 UFunion(p, q); 16 printf("%d %d\n",p, q); 17 } 18 */ 19 while(scanf("%d %d", &p, &q)==2) 20 { 21 if(UFunion(p, q)) 22 { 23 printf("%d %d\n",p, q); 24 } 25 } 26 //printf("%d",UFnum(0, N)); 27 return 0; 28 }