关键：从最大的天数往前开始建立连通图
思路：
以天数为表头建立邻接表
取出最大和最小的天数，从最大的天数开始往前计算，一直算到最小的天数， 如果某一天t将两个不连通的小岛连接起来则该天会收到*；如果某条边连接的岛是相连 ，则不做任何处理
已知n个点的最小连通图的边数最少为n-1条，当连接的边数为n-1时所有岛相连，也就是说在该天之前都不会收到* ，完成检索
#include <iostream>
#include <cstring>
using namespace std;
#define MAXN 10005
#define MAXM 100005
#define MAXT 100005
struct node{
int d,u,v,next;
}edge[MAXM];
int head[MAXT],fa[MAXN];
int n,m,t,ma,mi;
int cnt,ans,sum;
void add(int t,int a,int b)
{
node E={t,a,b,head[t]};
edge[cnt]=E;
head[t]=cnt++;
}
void init(int n)
{
for (int i=1;i<=n;i++)
fa[i]=i;
}
int find(int x)
{
if (x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
void connected()
{
int fu,fv,h=-1,p;
for (int i=ma;i>=mi;i--)
{
p=0;
for (int j=head[i];j!=-1;j=edge[j].next)
{
fu=find(edge[j].u);
fv=find(edge[j].v);
if (fu!=fv)
{
ans++;
fa[fu]=fv;
p=1;
}
if (ans==n-1) //建立连接图成功
{
h=0;
break;
}
}
if (p==1) sum++;
if (h==0) break;
}
}
int main()
{
int t,a,b;
while (cin>>n>>m)
{
ma=0; mi=MAXT;
cnt=0; ans=0; sum=0;
memset(head,-1,sizeof(head));
for (int i=0;i<m;i++)
{
cin>>a>>b>>t;
add(t,a,b);
if(t>ma) ma=t;
else if(t<mi) mi=t;
}
init(n);
connected();
cout<<sum<<endl;
}
return 0;
}