kruskala

#include<algorithm>

#include<iostream>

using namespace std;

6int tab[100], ile[100];

8int Find(int a)

9{

10return (tab[a]==a) ? a : (tab[a] = Find(tab[a]));

11}

12

13bool Union(int a, int b)

14{

15int fa = Find(a); 

16int fb = Find(b);18

 

 if (fa==fb) return false;

19if (ile[fa] <= ile[fb])

20{

21ile[fb] += ile[fa];

22tab[fa] = fb;

23}

24else

25{

26ile[fa] += ile[fb];

27tab[fb] = fa;

28}

29return true;

30}

31

32 pair< int,pair<int,int> > krawedzie[300000]; 

34int main()

35{

36int n, m, a,b,c,koszt=0;

38cout<<"Podaj liczbe wierzcholkow i krawedzi"<<endl;

39	cin>>n>>m;
40

41for (int i=0; i<n; i++)

42{

43tab[i] = i; 

44ile[i] = 1; 

45}

46for (int i=0; i<m; i++)

47{

48cout<<"Podaj wierzcholki krawedzi i jej wage"<<endl;

49cin>>a>>b>>c;

50krawedzie[i] = make_pair( c, make_pair(a,b) );

51}

52

53sort(krawedzie, krawedzie+m);

54cout<<endl;

55

56for (int i=0; i<m; i++)

57if(Union(krawedzie[i].second.first,krawedzie[i].second.second))

58{

59	cout<<krawedzie[i].second.first<<" - "<<krawedzie[i].second.second<<" : "
<<krawedzie[i].first<<endl;
60	koszt += krawedzie[i].first; //koszt (c)

61}

62cout<<koszt;

63return 0;

64 }