合并-查找接口实现

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 }