本文共 3940 字，大约阅读时间需要 13 分钟。

首先要提到，关于并查集的路径压缩，我之前都是直接找路径的，如果优化的话，就是需要有路径压缩，

也就是在找祖宗的时候，也就是 a[x]=zuzong(a[x]) 试着解释一下这个路径压缩，也就是当找x的祖宗，发现他的a[x]不等于x的时候，说明x和a[x]不是同一个，所以需要找a[x}的祖宗，所以可以先把zuzong(a[x]）预存在a[x]中，其实相当于做了两步的zuzog(a[x]）

题目1：（这道题要注意，memset不能直接初始化1.。。）

题目的大意就是：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;//我的思路就是，先初始化一个count为1//为一是因为刚开始就有一个人，然后判断这几组是否能连起来，如果连起来，count就加一//现在问题是，怎么判断他们来自同一组？或者就是再设置一个max//看了一下解析，可以用这个方法，就是记录一个集合的人数，刚开始都是初始化为1//然后判断这几组朋友在不在同一个集合，如果他们在，就不用变化，如果不在的话，阿九把他们弄到同一个集合，并且//把对应记录数组的那个最根节点设置为1int a[10000];int num[10000];//一个是存根节点，一个是存根节点的对应人数//写一个方法找他们的zuzong，并路劲压缩int zuzong(int x){ if(a[x]==x) return x; else{ a[x]=zuzong(a[x]); return zuzong(a[x]);//这就是路径压缩 }}//再写一个判断他们是不是同一个祖宗bool judge(int x,int y){ return zuzong(x)==zuzong(y);}//再写一个合并操作void merge(int x,int y){ //这里的合并就不需要判断是不是同一个祖宗了，因为进行合并的前提就是他们不是同一个祖宗 a[zuzong(x)]=zuzong(y);}int main(){ //先初始化a和sum,一个是自己，一个是全为1 int i; for(i=0;i<10000;i++) a[i]=i; //memset(num,1,sizeof(num));//果然是这里出现了问题，不能直接初始化为1 for(i=0;i<10000;i++) num[i]=1; int n;//有好几组数据 int f1,f2;//表示每组的两个小朋友 int mmax=0; while(scanf("%d",&n)!=EOF){ //n表示有n队好朋友，其实相当于就是把这对朋友并查集合到一起 while(n--){ scanf("%d%d",&f1,&f2); if(!judge(f1,f2)){ //如果他们不是同一个祖宗，那就合并，并且对同一个祖宗的sum++ merge(f1,f2); // printf("%d %d\n",num[zuzong(f1)],num[zuzong(f2)]); num[zuzong(f1)]+=num[zuzong(f2)]; //printf("%d %d\n",num[zuzong(f1)],num[zuzong(f2)]); } } //开始找最大值，遍历所有的num for( int j=0;j<10000;j++){ if(num[j]>mmax) mmax=num[j]; } printf("%d\n",mmax); }}
        
       
      
     
    
   

题2 最小生成树：

这题我之前有写过：

题3：（这道题还挺好的）

题目大致意思：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;//我对这道题的想法就是，需要创建一个结构体数组，把二维变成一维，然后在结构体数组中有，起始点，和终点以及他们之间的距离。//这道题的难点在于，二维变成一维。可以再创建一个结构体来对x和y吧，所以先创建一个结构体是是用来存这个点的，在创建一个结构体是用来//存起点，终点，以及他们的距离struct M{ double x,y;}Po[20];struct D{ int s; int e; double dis;//分别是起点终点和距离}Shen[50];int a[100];//写一个方法找他们的zuzong，并路劲压缩int zuzong(int x){ if(a[x]==x) return x; else{ a[x]=zuzong(a[x]); return zuzong(a[x]);//这就是路径压缩 }}//再写一个判断他们是不是同一个祖宗bool judge(int x,int y){ return zuzong(x)==zuzong(y);}//再写一个合并操作void merge(int x,int y){ //这里的合并就不需要判断是不是同一个祖宗了，因为进行合并的前提就是他们不是同一个祖宗 a[zuzong(x)]=zuzong(y);}//再写一个求距离的方法double lon(double x1,double y1,double x2,double y2){ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}bool cmp(D a,D b){ return a.dis
        
       
      
     
    
   

开始写最短路径

有写过类似的，但是好像发现这道题没写过

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;//弗洛伊德算法走起 dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j])int main(){ int i,j,k; int n,m;//分别代表n个路口，和m条路 int dis[25][25]={ 100};//初始化都很长 int s,e,l;//分别代表起点，终点和距离（在这题中相当于就是时间） while(scanf("%d%d",&n,&m)!=EOF&&n!=0&&m!=0){ for(i=0;i
        
       
      
     
    
   

最后一部分：拓扑排序

没有写这道题，而是参考了《算法笔记》里的题，题目链接： 而且这个解析我觉得很不错

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;//对于拓扑排序来说，首先是使用到栈，其次便是对于入队和出度的一些东西的记录//首先是创建一个存储每个点信息的结构体数组struct Node{ int Size;//表示的是序列 int innum;//入度的数量 int outnum[20];//表示这个点可以到对应的哪些点}node;int main(){ int i,j,n; scanf("%d",&n); int Map[100][100];//这个是用来存数据的 //再创建结构体数组 Node XH[100];//就是那些对应的点 //对这些点进行初始化 for(i=1;i<=n;i++){ XH[i].innum=0;//入度全为0 XH[i].Size=i-1;//先不按照那个，直接自己写,这个其实算是为了照顾输出 for( j=0;j
          
            p; //先把所有入度为0的点都加入栈中 for(i=1;i<=n;i++){ if(XH[i].innum==0) p.push(XH[i]); } int cou=0;//记录入栈的数量 Node temp;//中间结构体数组 int result[100]={ 0}; int flag=0;//这两个是用来记录最后结果的 while(!p.empty()){ //如果栈非空的话 temp=p.top();//Temp代表栈顶元素 result[flag++]=temp.Size;//这个就是用来代表当前的序列（其实和点的意思差不多） //再把栈顶元素删除 p.pop(); cou++;//出栈的个数加一 //然后把和这个temp有关的点，入队全都减去一,也就是找temp的出站那个数组，还有数 for(i=0;temp.outnum[i]!=0;i++){ XH[temp.outnum[i]].innum--; //如果为此这个点入度也变成了0，那就进栈 if(XH[temp.outnum[i]].innum==0){ p.push(XH[temp.outnum[i]]); } } } //最后结果开始判断 if(cou
          
         
        
       
      
     
    
   

转载地址：http://yyfen.baihongyu.com/