e has the largest weight in a cycle, then e does not belong to any minimum spanning tree
w is the maximum weight on the path from u → v, then all paths from u → v in the original graph have a maximum weight greater than w
e is the edge with the smallest weight in the graph, then it belongs to every minimum spanning tree
O(log(E))
// Kruskal's Algorithm for Minimum Spanning Tree
#include <bits/stdc++.h>
#define pp push_back
using namespace std;
using ll = long long;
const int maxn = 1e5+5;
int n,m,dsu[maxn],sz[maxn],cnt=0;
ll ans;
struct node
{
int u, v, w;
};
vector <node> e;
bool cmp(node x, node y)
{
return x.w<y.w;
}
// Disjoint Set Union (DSU) functions
int find_set(int u)
{
if(dsu[u]==u) return u;
else return dsu[u]=find_set(dsu[u]);
}
void unite(int u, int v, int w)
{
int id=find_set(u), id1=find_set(v);
if(id!=id1)
{
if(sz[id]>=sz[id1])
{
sz[id]+=sz[id1];
dsu[id1]=id;
}
else
{
sz[id1]+=sz[id];
dsu[id]=id1;
}
ans+=w;
++cnt;
}
}
void input()
{
cin>>n>>m;
for(int i=1;i<=n;++i)
{
dsu[i]=i;
sz[i]=1;
}
for(int i=1,u,v,w;i<=m;++i)
{
cin>>u>>v>>w;
node tmp;
tmp.u=u;
tmp.v=v;
tmp.w=w;
e.pp(tmp);
}
sort(all(e),cmp);
for(node i : e) unite(i.u,i.v,i.w);
if(cnt==n-1) cout<<ans;
else cout<<-1;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
input();
return 0;
}
dis[i] representing the shortest distance from the skeleton tree to vertex i. After each iteration, add vertex i with the smallest dis[i] to the skeleton tree and update the adjacent dis[j] values.
O(n^2 + E)
// Prim's Algorithm for Minimum Spanning Tree
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pp push_back
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using pii = pair <int,int>;
const char el ='\n';
const char sp = ' ';
const int maxn = 1e5+5, inf = 1e9+1;
int n,m,d[maxn];
bool mark [maxn];
vector <pii> adj[maxn];
ll ans;
void Prim()
{
d[1]=0;
int cnt = 0;
while(cnt<n)
{
int mn = inf, id;
for(int i=1;i<=n;++i){
if(!mark[i] && d[i]<mn){
mn = d[i];
id = i;
}
}
++cnt;
mark[id] = true;
ans +=mn;
for(pii i : adj[id]) d[i.ff] = min(d[i.ff],i.ss);
}
cout<<ans;
}
void input()
{
cin>>n>>m;
fill(d,d+n+1,inf);
for(int i=1,u,v,w;i<=m;++i)
{
cin>>u>>v>>w;
adj[u].pp({v,w});
adj[v].pp({u,w});
}
Prim();
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
input();
return 0;
}