蓝桥杯历届试题 国王的烦恼(并查集+快排)------C语言—菜鸟级

`#include<stdio.h> 
long int f[10002];
struct node
{ long int a,b,t;
} s[100003];
void init(long int n)//初始化 
{ long int i;
  for(i=1;i<=n;i++)
    f[i]=i;
}
long int ftop(long int x)//寻根节点 
{   long int t,tx=x;
   while(tx!=f[tx])tx=f[tx];
   while(x!=tx)
   {   t=f[x];
       f[x]=tx;
       x=t;
   }
   return tx;
}
int find(long int x,long int y)
{  
      x=ftop(x);
      y=ftop(y);
      if(y!=x)//判断是否在同一集合 
      { f[y]=x;
       return 1; 
      }
      return 0;
}
 void swp(long int x,long int y)//快排 
 { struct node te=s[x];s[x]=s[y];s[y]=te;}
    
    long  int kp(long int ks,long int js)
    {    long int x=s[ks].t;
       long int i=ks,j=js+1;
       while(1)
       {  while(s[++i].t<x&&i<js);
          while(s[--j].t>x);
          if(i<j)swp(i,j);
          else break;
       }
       swp(ks,j);
       return j;
    }
 void ppp(long int ks,long int js)
 { long int r;
     if(ks<js)
     {  r=kp(ks,js);
        ppp(ks,r-1);
        ppp(r+1,js);
     }
 }
int main()
{
 long int n,m,i,j,sum=0,pre=-1;
 scanf("%ld%ld",&n,&m);
 init(n);
for(i=1;i<=m;i++)
scanf("%ld%ld%ld",&s[i].a,&s[i].b,&s[i].t);
ppp(1,m);//快排 
 for(i=m;i>=1;i--)
if(find(s[i].a,s[i].b)&&s[i].t!=pre)sum++,pre=s[i].t;
 printf("%ld\n",sum);
return 0;
}`