Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- using namespace std;
- ifstream f("kruskal.in");
- ofstream g("kruskal.out");
- int n,m,M[100],p,cost=0;
- struct muchie
- {
- int x,y,c;
- }v[100],aux;
- void citire()
- {
- int i;
- f>>n>>m;
- for(i=1;i<=m;i++)
- {
- f>>v[i].x;
- f>>v[i].y;
- f>>v[i].c;
- }
- }
- void quicksort(int s,int d)
- {
- int i,j,pivot;
- if(s<d)
- {
- i=s;
- j=d;
- pivot=v[s].c;
- while(i<j)
- {
- while(pivot>=v[i].c) i++;
- while(pivot<v[j].c) j--;
- if(i<j)
- {
- aux=v[i];v[i]=v[j];v[j]=aux;
- }
- }
- aux=v[s];
- v[s]=v[j];
- v[j]=aux;
- quicksort(s,j-1);
- quicksort(j+1,d);
- }
- }
- int main()
- {
- int i,j;
- citire();
- quicksort(1,m);
- for(i=1;i<=n;i++)
- {
- M[i]=i;
- }
- i=1;
- p=0;
- while(p<n-1)
- {
- if(M[v[i].x]!=M[v[i].y])
- {
- p++;
- g<<v[i].x<<" "<<v[i].y<<"\n";
- cost=cost+v[i].c;
- int a=M[v[i].x];
- int b=M[v[i].y];
- for(j=1;j<=n;j++)
- {
- if(M[j]==b) M[j]=a;
- }
- }
- i++;
- }
- g<<"Costul total: "<<cost;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement