蓝桥杯历届试题-国王的烦恼 （C语言代码）-----------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;
}