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