问题描述 C国由n个小岛组成，为了方便小岛之间联络，C国在小岛间建立了m座大桥，每座大桥连接两座小岛。两个小岛间可能存在多座桥连接。然而，由于海水冲刷，有一些大桥面临着不能使用的危险。
如果两个小岛间的所有大桥都不能使用，则这两座小岛就不能直接到达了。然而，只要这两座小岛的居民能通过其他的桥或者其他的小岛互相到达，他们就会安然无事。但是，如果前一天两个小岛之间还有方法可以到达，后一天却不能到达了，居民们就会一起*。
现在C国的国王已经知道了每座桥能使用的天数，超过这个天数就不能使用了。现在他想知道居民们会有多少天进行*。 输入格式 输入的第一行包含两个整数n, m，分别表示小岛的个数和桥的数量。
接下来m行，每行三个整数a, b, t，分别表示该座桥连接a号和b号两个小岛，能使用t天。小岛的编号从1开始递增。 输出格式 输出一个整数，表示居民们会*的天数。 样例输入 4 4
1 2 2
1 3 2
2 3 1
3 4 3 样例输出 2 样例说明 第一天后2和3之间的桥不能使用，不影响。
第二天后1和2之间，以及1和3之间的桥不能使用，居民们会*。
第三天后3和4之间的桥不能使用，居民们会*。 数据规模和约定 对于30%的数据，1<=n<=20，1<=m<=100；
对于50%的数据，1<=n<=500，1<=m<=10000；
对于100%的数据，1<=n<=10000，1<=m<=100000，1<=a, b<=n， 1<=t<=100000。
题目解析：
开始的时候还SB的认为是只有一个岛屿全部的桥废掉才会*，然后排序，查找，果断WR（竟然还对了30%，醉了
），其实是在出现新的连通分支的时候就要是*的一天了。。。喜欢贴上曾经错误的代码，至少可以留一点屌丝的回忆不是么。。。
错误代码：
#include<iostream>
#include<string>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int island[10005],leftisland;//剩下的岛屿
struct Br{
int x1,x2,day;
}bri[100005];
bool cmp(Br a,Br b){
return a.day<b.day;
}
int main(){
int n,m;
int day = 1,leftbri,count=1,fightday=0;//计天数 剩下的桥梁 桥梁计数 *天数
memset(island,0,sizeof(island));
cin>>n>>m;
leftbri = m;
for(int i=1;i<=m;i++){
cin>>bri[i].x1>>bri[i].x2>>bri[i].day;
island[ bri[i].x1 ]++,island[ bri[i].x2 ]++;
}
sort(bri+1,bri+m+1,cmp);
while(leftbri>0){
int mark=1;
if(bri[count].day==day)
while(leftbri>0&&bri[count].day==day){
island[ bri[count].x1 ]--,island[ bri[count].x2 ]--;
if( mark==1&&day!=1&&island[ bri[count].x1 ]==0) fightday++,mark=0;
if( mark==1&&day!=1&&island[ bri[count].x2 ]==0) fightday++,mark=0;
count++;
leftbri--;
}
day++;
}
cout<<fightday<<endl;
return 0;
}
题目最终转化为了求连通分支的数目，但是因为随这时间是要不断查找的，如果出现了一次时间就查找一次的话，并查集好像没有这么强大，并且时间也是不允许的，所以我们巧妙的转化一下，转化为按照时间的从后向前的顺序重新建一遍树，这样相当于逆向的把树重新建了一遍，成功的在一次遍历的时候就完成了建树过程，逆向完成。。。
代码：
#include <iostream>一直不太习惯写Union函数，但是好像写了之后变得特别清晰，以后还是要这样多多联系写Union函数
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3
using namespace std;
int n,m;
int father[10005];
struct edge{
int u,v,c;
}e[100005];
int findf(int x){
return father[x]<0 ? x : father[x]=findf(father[x]);
}
bool cmp(edge a,edge b){
return a.c>b.c;
}
int main(){
cin>>n>>m;
for(int i=0;i<m;i++)
cin>>e[i].u>>e[i].v>>e[i].c;//分别输入的是根节点和子节点
sort(e,e+m,cmp);//按照维持天数从大到小排序
memset(father,-1,sizeof(father));
// cout<<endl<<endl;
// for(int i=0;i<m;i++)
// cout<<e[i].u<<' '<<e[i].v<<' '<<e[i].c<<endl;
int sum=0,time=-1 ;
for(int i=0;i<m;i++){
int xx=findf(e[i].u),yy=findf(e[i].v);
if(xx!=yy){
father[xx]=yy;
if(time!=e[i].c){
time=e[i].c;
sum++;
}
}
}
cout<<sum<<endl;
return 0;
}
贴一下网友比较偏亮的代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#define maxn 10000+5
#define maxm 100000+5
using namespace std;
int f[maxn],lastday;
struct node
{
int x, y, v;
} N[maxm];
bool cmp (node a,node b){
return a.v>b.v;
}
int Find(int x){ //找 x 所在的树根
return f[x]==x?x:f[x]=Find(f[x]);
}
bool Union(int x, int y){
int tx=Find(x),ty=Find(y);
if(tx==ty) return false; //它俩在同一个连通分量
f[tx]=ty; //合并两个连通分量
return true;
}
int main(){
int n, m;
while(~scanf("%d%d",&n,&m)) {
for(int i=0;i<m;i++)
scanf("%d%d%d",&N[i].x,&N[i].y,&N[i].v);
sort(N,N+m,cmp);
for(int i=0;i<=n;i++)
f[i]=i; //初始化并查集
int cnt=0;
lastday=-1;
for(int i=0;i<m;i++) {
if(Union(N[i].x,N[i].y) && N[i].v!=lastday){ //两个小岛不连通，且与上一个大桥的天数不同
cnt++;
lastday=N[i].v;
}
}
printf("%d\n", cnt);
}
return 0;
}
下面再做一下小总结：
关于并查集在树的连通性上发挥着巨大的作用，能够在查的同时实现和并，简化时间复杂度，另外深刻的认识到并查集远不止用来建树的，完全可以向这道题一样把拆树想象成逆向的建树，这样就完成了转化，照样可是实现问题的完美解决。
另外最近发现以下感觉和以前做过的类型相似的，但是好像又不一样，这样的话不知道怎么入手，那么就可以逆向思维，或许就会柳暗花明了。。。