1 #include <stdio.h> 2 int h[ 101];//用来存放堆的数组 3 int n;//用来存储堆中元素的个数，也就是堆的大小 4  5  6 //交换函数，用来交换堆中的两个元素的值 7 void swap(int x,int y) 8 { 9     int t;10     t=h[ x];11     h[ x]=h[ y];12     h[ y]=t;13 }14 15 16 //向下调整函数17 void siftdown(int i) //传入一个需要向下调整的结点编号i，这里传入1，即从堆的顶点开始向下调整18 {19     int t,flag=0;//flag用来标记是否需要继续向下调整20     //当i结点有儿子的时候（其实是至少有左儿子的情况下）并且有需要继续调整的时候循环窒执行21     while( i*2<=n && flag==0 )22     {        23         //首先判断他和他左儿子的关系，并用t记录值较小的结点编号24         if( h[ i] > h[ i*2] )25             t=i*2;26         else27             t=i;28         //如果他有右儿子的情况下，再对右儿子进行讨论29         if(i*2+1 <= n)30         {31             //如果右儿子的值更小，更新较小的结点编号  32             if(h[ t] > h[ i*2+1])33                 t=i*2+1;34         }35         //如果发现最小的结点编号不是自己，说明子结点中有比父结点更小的  36         if(t!=i)37         {38             swap(t,i);//交换它们，注意swap函数需要自己来写39             i=t;//更新i为刚才与它交换的儿子结点的编号，便于接下来继续向下调整40         }41         else42             flag=1;//则否说明当前的父结点已经比两个子结点都要小了，不需要在进行调整了43     }44 }45 46 47 //建立堆的函数48 void creat()49 {50     int i;51     //从最后一个非叶结点到第1个结点依次进行向上调整52     for(i=n/2;i>=1;i--)53     {54         siftdown(i);55     }  56 }57 58 59 //删除最大的元素60 int deletemax()61 {62     int t;63     t=h[ 1];//用一个临时变量记录堆顶点的值64     h[ 1]=h[ n];//将堆得最后一个点赋值到堆顶65     n--;//堆的元素减少166     siftdown(1);//向下调整67     return t;//返回之前记录的堆得顶点的最大值68 }69 70 71 int main()72 {73     int i,num;74     //读入数的个数75     scanf("%d",&num);76 77 78     for(i=1;i<=num;i++)79         scanf("%d",&h[ i]);80     n=num;   81 82     //建堆83     creat();84 85     //删除顶部元素，连续删除n次，其实夜就是从大到小把数输出来86     for(i=1;i<=num;i++)87         printf("%d ",deletemax());88 89     getchar();90     getchar();91     return 0;92 }93 94 /*95 96 1497 99 5 36 7 22 17 46 12 2 19 25 28 1 9298 99 */

  1 #include <stdio.h>  2 int h[ 101];//用来存放堆的数组  3 int n;//用来存储堆中元素的个数，也就是堆的大小  4   5   6 //交换函数，用来交换堆中的两个元素的值  7 void swap(int x,int y)  8 {  9     int t; 10     t=h[ x]; 11     h[ x]=h[ y]; 12     h[ y]=t; 13 } 14  15  16 //向下调整函数 17 void siftdown(int i) //传入一个需要向下调整的结点编号i，这里传入1，即从堆的顶点开始向下调整 18 { 19     int t,flag=0;//flag用来标记是否需要继续向下调整 20     //当i结点有儿子的时候（其实是至少有左儿子的情况下）并且有需要继续调整的时候循环窒执行 21     while( i*2<=n && flag==0 ) 22     {         23         //首先判断他和他左儿子的关系，并用t记录值较大的结点编号 24         if( h[ i] < h[ i*2] ) 25             t=i*2; 26         else 27             t=i; 28         //如果他有右儿子的情况下，再对右儿子进行讨论 29         if(i*2+1 <= n) 30         { 31             //如果右儿子的值更大，更新较小的结点编号   32             if(h[ t] < h[ i*2+1]) 33                 t=i*2+1; 34         } 35         //如果发现最大的结点编号不是自己，说明子结点中有比父结点更大的   36         if(t!=i) 37         { 38             swap(t,i);//交换它们，注意swap函数需要自己来写 39             i=t;//更新i为刚才与它交换的儿子结点的编号，便于接下来继续向下调整 40         } 41         else 42             flag=1;//则否说明当前的父结点已经比两个子结点都要大了，不需要在进行调整了 43     } 44 } 45  46  47 //建立堆的函数 48 void creat() 49 { 50     int i; 51     //从最后一个非叶结点到第1个结点依次进行向上调整 52     for(i=n/2;i>=1;i--) 53     { 54         siftdown(i); 55     }   56 } 57  58  59 //堆排序 60 void heapsort() 61 { 62     while(n>1) 63     { 64         swap(1,n); 65         n--; 66         siftdown(1); 67     } 68 } 69  70  71 int main() 72 { 73     int i,num; 74     //读入n个数 75     scanf("%d",&num); 76  77  78     for(i=1;i<=num;i++) 79         scanf("%d",&h[i]); 80     n=num;    81  82  83     //建堆 84     creat(); 85  86  87     //堆排序 88     heapsort(); 89  90  91     //输出 92     for(i=1;i<=num;i++) 93         printf("%d ",h[i]); 94  95  96     getchar(); 97     getchar(); 98     return 0; 99 }100 101 /*102 103 14104 99 5 36 7 22 17 46 12 2 19 25 28 1 92105 106 */

 1 #include <stdio.h> 2 int f[1000]={0},n,m,k,sum=0; 3  4 void init() 5 { 6   int i; 7   for(i=1;i<=n;i++) 8     f[i]=i; 9 }10 11 int getf(int v)12 {13   if(f[v]==v)14     return v;15   else16   {17     f[v]=getf(f[v]);18     return f[v];19   }20 }21 22 void merge(int v,int u)23 {24   int t1,t2;25   t1=getf(v);26   t2=getf(u);27   if(t1!=t2)28   {29     f[t2]=t1;30   }31 }32 33 int main()34 {35   int i,x,y;36   scanf("%d %d",&n,&m);37   38   init();39   for(i=1;i<=m;i++)40   {41     scanf("%d %d",&x,&y);42     merge(x,y);43   }44   45   for(i=1;i<=n;i++)46   {47     if(f[i]==i)48       sum++;49   }50   printf("%d\n",sum);51 52   getchar(); getchar();53   return 0;54 }55 56 /*57 58 10 959 1 260 3 461 5 262 4 663 2 664 8 765 9 766 1 667 2 468 69 */