Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- ifstream fin("kruskal.in");
- ofstream fout("kruskal.out");
- struct muchie
- {
- int x,y,c;
- };
- muchie a[1001];
- struct afis
- {
- int x,y;
- };
- afis v[1001];
- int t[1001],n,m;
- void Union(int x,int y)
- {
- t[y]=x;
- }
- int Find(int x)
- {
- int rad,y;
- rad=x;
- while(t[rad]!=0) rad=t[rad];
- while(x!=rad)
- {
- y=t[x];
- t[x]=rad;
- x=y;
- }
- return rad;
- }
- void Citire()
- {
- int i;
- fin>>n>>m;
- for(i=1;i<=m;i++) fin>>a[i].x>>a[i].y>>a[i].c;
- }
- bool Cmp(muchie A, muchie B)
- {
- return A.c<B.c;
- }
- void Kruskal()
- {
- int p,q,costmin,cnt=1;
- sort(a+1,a+m+1,Cmp);
- costmin=0;
- for(int i=1;i<=m;i++)
- {
- p=Find(a[i].x);
- q=Find(a[i].y);
- if(p!=q)
- {
- v[cnt].x=a[i].x;
- v[cnt].y=a[i].y;
- cnt++;
- costmin+=a[i].c;
- Union(p,q);
- }
- }
- fout<<costmin<<"\n";
- for(int i=1;i<cnt;i++) fout<<v[i].x<<" "<<v[i].y<<"\n";
- }
- int main()
- {
- Citire();
- Kruskal();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement