蓝桥杯历届试题国王的烦恼(并查集+快排)

解题思路：采用并查集的思想，逆向的将树建一遍，所以这里我需要对天数排序，
从大到小进行排序。接着进行建树，在建树的过程中不断地进行判断，我之前是否有
这个桥，如果没有那么就抗议次数++。这里还有一个需要注意的就是：前一次是在
第几天抗议的，如果是同一天的话就不要++了，所以这里要特殊判断一下。

详见代码。

`#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;}

<span class="token keyword">long</span>  <span class="token keyword">int</span> <span class="token function">kp</span><span class="token punctuation">(</span><span class="token keyword">long</span> <span class="token keyword">int</span> ks<span class="token punctuation">,</span><span class="token keyword">long</span> <span class="token keyword">int</span> js<span class="token punctuation">)</span>
<span class="token punctuation">{</span>    <span class="token keyword">long</span> <span class="token keyword">int</span> x<span class="token operator">=</span>s<span class="token punctuation">[</span>ks<span class="token punctuation">]</span><span class="token punctuation">.</span>t<span class="token punctuation">;</span>
   <span class="token keyword">long</span> <span class="token keyword">int</span> i<span class="token operator">=</span>ks<span class="token punctuation">,</span>j<span class="token operator">=</span>js<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>
   <span class="token keyword">while</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">)</span>
   <span class="token punctuation">{</span>  <span class="token keyword">while</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span><span class="token operator">++</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>t<span class="token operator">&lt;</span>x<span class="token operator">&amp;&amp;</span>i<span class="token operator">&lt;</span>js<span class="token punctuation">)</span><span class="token punctuation">;</span>
      <span class="token keyword">while</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span><span class="token operator">--</span>j<span class="token punctuation">]</span><span class="token punctuation">.</span>t<span class="token operator">&gt;</span>x<span class="token punctuation">)</span><span class="token punctuation">;</span>
      <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">&lt;</span>j<span class="token punctuation">)</span><span class="token function">swp</span><span class="token punctuation">(</span>i<span class="token punctuation">,</span>j<span class="token punctuation">)</span><span class="token punctuation">;</span>
      <span class="token keyword">else</span> <span class="token keyword">break</span><span class="token punctuation">;</span>
   <span class="token punctuation">}</span>
   <span class="token function">swp</span><span class="token punctuation">(</span>ks<span class="token punctuation">,</span>j<span class="token punctuation">)</span><span class="token punctuation">;</span>
   <span class="token keyword">return</span> j<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
 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;
}`