蓝桥杯历届试题 国王的烦恼(并查集+快排)------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;
}`

  

 

  
 
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
 

文章来源: fivecc.blog.csdn.net，作者：Five-菜鸟级，版权归原作者所有，如需转载，请联系作者。

原文链接：fivecc.blog.csdn.net/article/details/79957857