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
| namespace Kruskal{
const int MAXN = 1e5+5;
const int MAXM = 1e5+5;
int n,m,k,a,b,c,fa[MAXN],tot;
struct Edge{
int f,t,dis;
bool operator < (const Edge &oth) const{
return dis<oth.dis;
}
}edge[MAXM];
inline void add(int f, int t, int d){
edge[++tot].f = f;
edge[tot].t = t;
edge[tot].dis = d;
}
inline int Find(int x){
while(x!=fa[fa[x]]) x = fa[x] = Find(fa[fa[x]]);
return x;
}
inline void Union(int x, int y){
fa[Find(x)] = Find(y);
}
inline int connect(){
for(int i=1;i<=n;i++) fa[i] = i;
int re = 0;
sort(edge+1,edge+1+tot);
for (int i=1;i<=tot;i++){
if (k==n-1) break;
int f = edge[i].f, t = edge[i].t, d = edge[i].dis;
if(Find(f)!=Find(t)) {re+= d; Union(f,t);k++;}
}
return re;
}
inline void init();
inline void solve();
}
|
