关键：从最大的天数往前开始建立连通图
思路：
以天数为表头建立邻接表
取出最大和最小的天数，从最大的天数开始往前计算，一直算到最小的天数， 如果某一天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; }