#include <algorithm>
#include <iostream>
#include <vector>
#include <list>
using namespace std;

//-----------------------------------------------------------------------
//
// Grafta bulunan ayrıt, her iki ucundan da bir düğüme bağlıdır. Bu
// düğümlerin numaraları d1 ve d2'dir. ayrıtın ağırlığı ise w'dir.
// Ayrıca ayrıtın minimum örten ağaç içinde bulunup bulunmadığını
// anlamak için bir adet lojik değişken kullanılmıştır.
//
//-----------------------------------------------------------------------

struct ayrit
{
bool kullanimda;
int w;
int d1;
int d2;

// ayrit sınıfı için yapıcı.
ayrit (int id1, int id2, int agirlik) : d1 (id1), d2 (id2), w (agirlik)
{
kullanimda = false; // ayrıt ilk başta ağaca dahil değil
}
};

//------------------------------ prim -----------------------------------
//
// Amaç : Verilen grafın minimum kapsayan ağacını bulmak
//
// Giriş parametresi : Üzerinde çalışılan graf
//
// Dönüş değeri : Minimum örten ağaca ait ayrıtları tutan vektör
//
// Fonksiyonda minimum örten ağacı bulma işlemi, prim algoritması ile
// gerçeklenmiştir.
//
//-----------------------------------------------------------------------

vector<ayrit> prim (vector<ayrit>& G)
{
vector<ayrit> S; // Sonucu tutmak için
list<int> D; // Graftaki düğümlerin numaralarını tutmak için

// Graf üzerindeki düğümler listeye ekleniyor
for (int i = 0; i < G.size (); i ++)
{
D.push_back (G[i].d1);
D.push_back (G[i].d2);
}

// Aynı numaraya sahip olanlar listeden çıkarılıyor
D.sort ();
D.unique ();

// Minimum örten ağacı oluşturmaya başlamak için bir düğüm seçiliyor.
// Ağaç bu düğümden başlayarak genişleyecek.
D.remove (G[0].d1);

while (1)
{
// while döngüsünün her dönüşünde, ağaca eklenebilecek durumda
// olan ayrıtlardan, minimum ağırlıkta olanı araştırılıyor.

int min = RAND_MAX;
int ayritNo = -1;

// Graftaki tüm ayrıtlara tek tek bak
for (i = 0; i < G.size (); i ++)
{
// Bu ayrıt kullanımda mı?
if (!G[i].kullanimda)
{
// Bu ayrıt daha önce ağaca eklemek için bulduğum uygun
// ayrıta göre daha mı hafif?
if (G[i].w < min)
{ 
// Bu ayrıtın her iki ucundaki düğüm de daha önce ağaca
// eklenmiş düğümlerin uçlarıysa, bu ayrıtı ağaca
// eklediğimizde bir çevre oluşturacaktır. Bu yüzden
// böyle bir ayrıtı ağaca eklememek gerekiyor.
// Buradaki D vektörü henüz hiç kullanılmamış düğümleri
// tutar. Eğer bir düğüm minimum örten ağaç içinde
// kullanılırsa, o düğüm bu vektörden silinir.
// Aşağıdaki ifler ile, eklemek istediğimiz ayrıtın iki
// ucundaki düğümlerden sadece birinin daha önceden
// kullanılmış olup olmadığı araştırılıyor. Böyle olunca,
// hem bu ayrıt ile mevcut ağaç arasında bir bağlantı
// olmuş olur, hem de eklenince çevre oluşturmaz.

int k = 0;

if (find (D.begin (), D.end (), G[i].d1) == D.end ()) k ++;
if (find (D.begin (), D.end (), G[i].d2) == D.end ()) k ++;

if (k == 1)
{
min = G[i].w;
ayritNo = i;
}
}
}
}

// Eğer eklenecek ayrıt kalmadıyda, fonksiyonu sonlandir.
if (ayritNo == -1) return S;

// Bu ayrıt artık kullanılıyor. Bir daha eklemeye çalışma!
G[ayritNo].kullanimda = true;

// d1 ve d2 nolu düğümleri düğüm listesinden sil. Bu düğümler
// artık kullanılmış düğümler.
D.remove (G[ayritNo].d1);
D.remove (G[ayritNo].d2);

// Elde edilen ayrıtı ağaca ekle
S.push_back (G[ayritNo]);
}

return S;
}

//------------------------------ main -----------------------------------

int main ()
{
vector<ayrit> S;
vector<ayrit> G;

// Graf oluşturuluyor.
G.push_back (ayrit (1, 2, 2));
G.push_back (ayrit (1, 3, 1));
G.push_back (ayrit (2, 3, 3));
G.push_back (ayrit (2, 4, 3));
G.push_back (ayrit (3, 4, 6));
G.push_back (ayrit (4, 5, 2));

S = prim (G);

return 0;
}