P1111 修复公路（kruscal+并查集）

 1 #include<iostream>
 2 #include<cstring>
 3 #include<climits>
 4 #include<algorithm>
 5 using namespace std;
 6 struct edge
 7 {
 8     int x,y,t;
 9 }a[100009];
10 bool cmp(edge a,edge b)
11 {
12     return a.t<b.t;
13 }
14 int fa[1009];
15 int finds(int x)
16 {
17     while(fa[x]!=x)
18     {
19         x=fa[x];
20     }
21     return x;
22 }//并查集find函数
23 int main(void)
24 {
25     std::ios::sync_with_stdio(false);
26     int n,m;
27     cin>>n>>m;
28     for(int i=0;i<m;i++)
29     {
30         cin>>a[i].x>>a[i].y>>a[i].t;
31     }
32     sort(a,a+m,cmp);
33     for(int i=1;i<=n;i++)
34     {
35         fa[i]=i;
36     }//并查集初始化
37     int ans=-1;
38     for(int i=0;i<m;i++)
39     {
40         int f1=finds(a[i].x);
41         int f2=finds(a[i].y);
42         if(f1!=f2)
43         {
44             ans=max(ans,a[i].t);
45             fa[f1]=f2;//union
46         }
47     }
48     int cnt=0;
49     for(int i=1;i<=n;i++)
50     {
51         if(fa[i]==i)
52             cnt++;
53     }
54     if(cnt>=2)
55         ans=-1;//不连通输出-1
56     cout<<ans;
57     return 0;
58 }