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

int marka[1005];
vector<int> mg1[1005],mg2[1005],mg3[1005],mg4[1005];

void dfs_obidji(int cvor)
{
    cout<<cvor<<" ";
    int i,x;  marka[cvor]=1;
    for(i=0;i<mg1[cvor].size();i++)  // prolazimo kroz sve susede cvora koji se trenutno posmatra
    {
        x=mg1[cvor][i];
        if(marka[x]==0) dfs_obidji(x); // pozivamo finkciju za obilazak za one susede koji jos nisu poseceni
    }
}
void dfs()
{
    int n,m,s,i,x,y;
    cout<<"Uneti redom broj cvorova i broj grana grafa i cvor od koga pocinje obilazak."<<endl;
    cout<<"Za svaku granu uneti cvorove koje povezuje."<<endl;
    cin>>n>>m>>s;   //s-polazni cvor
    for(i=1;i<=m;i++)
    {
       cin>>x>>y;
       mg1[x].push_back(y);  mg1[y].push_back(x);
    }
    cout<<"Cvorovi po redu pronalaska:"<<endl;
    for(i=1;i<=n;i++) marka[i]=0;
    dfs_obidji(s);

}
void bfs()
{
    int n,m,s,i,x,y,bfs_niz[1005];

    cout<<"Uneti redom broj cvorova i broj grana grafa i cvor od koga pocinje obilazak."<<endl;
    cout<<"Za svaku granu uneti cvorove koje povezuje."<<endl;

    cin>>n>>m>>s;   //s-polazni cvor
    for(i=1;i<=m;i++)
    {
       cin>>x>>y;
       mg2[x].push_back(y);  mg2[y].push_back(x);
    }

    for(i=1;i<=n;i++) marka[i]=0;

    int ti=1,tc,u;  marka[s]=1;
    bfs_niz[1]=s;   u=1;  // u je ukupan broj cvorova u nizu u nekom trenutku
    ti=1; // ti predstavlja trenutni indeks u bfs nizu
    while(ti<=n)
    {
        tc=bfs_niz[ti];   // tc je trenutni cvor koji posmatramo
        for(i=0;i<mg2[tc].size();i++)
        {
            x=mg2[tc][i];
            if(marka[x]==0) { u++; bfs_niz[u]=x; marka[x]=1;}
        }
        ti++;
    }

    cout<<"Cvorovi po redu pronalaska:"<<endl;
    for(i=1;i<=n;i++) cout<<bfs_niz[i]<<" ";
}
int topoloski_redosled[1005],ukupno;
void dfs_ts(int cvor)
{
    int i,x;  marka[cvor]=1;
    for(i=0;i<mg3[cvor].size();i++)
       {
         x=mg3[cvor][i];
        if(marka[x]==0) dfs_ts(x);
       }
    ukupno++; topoloski_redosled[ukupno]=cvor;
}
void toposort_dfs()
{
    cout<<"Uneti redom broj cvorova i broj grana usmerenog aciklicnog grafa."<<endl;
    cout<<"Za svaku granu uneti cvorove koje povezuje."<<endl;
    int n,m,i,j,x,y;

    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>x>>y;
        mg3[x].push_back(y);
    }
    for(i=1;i<=n;i++) marka[i]=0;
    for(int i=1;i<=n;i++)
    {
        if(marka[i]==0) dfs_ts(i);    // ukoliko je to potrebno ponovo pozivamo funkciju za obilazak jer ne moraju svi cvorovi da se upisu u niz pri prvom pozivu
    }
    cout<<"Topoloski redosled cvorova je:"<<endl;
    for(i=ukupno;i>=1;i--) cout<<topoloski_redosled[i]<<" ";
}
void toposort_kan()
{
    int red[1005],u=0,st[1005],i,j,n,m,x,y;

    cout<<"Uneti redom broj cvorova i broj grana usmerenog aciklicnog grafa."<<endl;
    cout<<"Za svaku granu uneti cvorove koje povezuje."<<endl;

    cin>>n>>m;
    for(i=1;i<=n;i++){st[i]=0; marka[i]=0;}

    for(i=1;i<=m;i++)
    { cin>>x>>y;  mg4[x].push_back(y); st[y]++;}

    for(i=1;i<=n;i++) marka[i]=0;

    for(i=1;i<=n;i++)  // postavljanje u red svih cvorova sa ulaznim stepenom 0
    { if(st[i]==0) {u++; red[u]=i;} }

    i=1;
    while(i<n)
    {
       int cvor=red[i];
       for(j=0;j<mg4[cvor].size();j++)
       {
           x=mg4[cvor][j]; st[x]--;
           if(st[x]==0)  {u++; red[u]=x;}    // ako je cvor "dosao" do ulaynog stepena 0 ubacujemo ga u red
       }
       i++;
    }
    cout<<"Topoloski redosled cvorova je:"<<endl;
    for(i=1;i<=n;i++) cout<<red[i]<<" ";
}
int roditelj[1005],h[1005];
int dsu_nadji(int x)
{
    if(x==roditelj[x]) return x;
    else return roditelj[x]=dsu_nadji(roditelj[x]);
}
void dsu_spoj(int x,int y)
{
    int a=dsu_nadji(x);
    int b=dsu_nadji(y);
    if(h[a]<h[b]) {roditelj[a]=b; h[b]=max(h[b],h[a]+1);}
    else {roditelj[b]=a; h[a]=max(h[a],h[b]+1);}
}
void dsu()
 {
    int n,m,i,p,x,y,a,b;
    cout<<"Uneti redom broj elemenata i broj operacija."<<endl;
    cout<<"Program podrzava dva tipa operacija:"<<endl;
    cout<<"Za operaciju nadji(x) uneti broj 1, a zatim x."<<endl;
    cout<<"Za operaciju spoj(x,y) uneti broj 2, a zatim xi y."<<endl;
    cin>>n>>m;

    for(i=1;i<=n;i++) roditelj[i]=i;  // u pocetku svaki element je sam u svom skupu i yato pisemo da je njegov roditelj bas on
    for(i=1;i<=m;i++)
    {
        cin>>p;
        if(p==1)
        {
            cin>>x;
            cout<<"Uneti element se nalazi u podstablu sa korenom "<<dsu_nadji(x)<<"."<<endl;
        }
        else
        {
            cin>>x>>y;
            a=dsu_nadji(x); b=dsu_nadji(y);
            if(a==b) cout<<"Uneti elementi su u istom podstablu."<<endl;
            else {dsu_spoj(a,b); cout<<"Uneti elementi iz podstabala "<<a<<" i "<<b<<" su spojeni.";}
        }
    }
}
struct grana{int a,b,v;} mg[1005];  // strukturu grana koristimo i u Kruskalovom i u Primovom algoritmu
vector <grana> mg5[1005];
struct uredi_prim
{
    bool operator()(const grana & l,const grana & d)
    {
        if(l.v>d.v) return 1;
        else return 0;
    }
};
priority_queue<grana,vector<grana>,uredi_prim> prim;

void primov_algoritam()
{
    int n,m,i,j,k,x,y,nc,MPS_suma=0;
    grana t;

    cout<<"Uneti redom broj cvorova i broj grana grafa."<<endl;
    cout<<"Za svaku granu uneti cvorove koje povezuje, a zatim i njenu tezinu."<<endl;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>x>>y>>t.v;
        t.a=x; t.b=y;  mg5[x].push_back(t);
        t.a=y; t.b=x;  mg5[y].push_back(t);
    }
    for(i=1;i<=n;i++) marka[i]=0;

    marka[1]=1;    // Za pocetni cvor uzimamo cvor sa indeksom 1.
    for(i=0;i<mg5[1].size();i++)  prim.push(mg5[1][i]);

    cout<<"Grane koje pripadaju minimalnom pokrivajucem stablu su:"<<endl;

    int u=1;    // u je trenutni broj izabranih cvorova
    while(u<n)  // kada trenutni broj postane n prekidamo algoritam
    {
      while(marka[prim.top().a]==1 && marka[prim.top().b]==1)  prim.pop();
      t=prim.top();  prim.pop();
      cout<<t.a<<" "<<t.b<<" "<<t.v<<endl;  MPS_suma+=t.v;

      nc=t.b; //nc je novi cvor koji se dodaje skupu cvorova koji su dosad iyabrani
      marka[nc]=1; u++;

      for(i=0;i<mg5[nc].size();i++)
       {
        x=mg5[nc][i].b;
        if(marka[x]==1) continue;    //ukoliko grana povezuje trenutni cvor i neki vec markirani cvor
        else prim.push(mg5[nc][i]);
       }
    }
    cout<<"Suma vrednosti grana koje pripadaju MPS je "<<MPS_suma<<"."<<endl;
}

int kruskal_roditelj[1005],kruskal_h[1005];
int kruskal_poredi(grana x,grana y)
{
    if(x.v<y.v) return 1;
    else return 0;
}
int kruskal_nadji(int x)
{
    if(x==kruskal_roditelj[x]) return x;
    else return kruskal_roditelj[x]=kruskal_nadji(kruskal_roditelj[x]);
}
void kruskal_spoj(int x,int y)
{
    int a=kruskal_nadji(x);
    int b=kruskal_nadji(y);

    if(kruskal_h[a]<kruskal_h[b]) {kruskal_roditelj[a]=b; kruskal_h[b]=max(kruskal_h[b],kruskal_h[a]+1);}
    else {kruskal_roditelj[b]=a; kruskal_h[a]=max(kruskal_h[a],kruskal_h[b]+1);}
}
void kruskal()
{
    int n,m,i,j,x,y,MPS_suma=0;

    cout<<"Uneti redom broj cvorova i broj grana grafa."<<endl;
    cout<<"Za svaku granu uneti cvorove koje povezuje, a zatim i njenu tezinu."<<endl;
    cin>>n>>m;
    for(i=1;i<=m;i++) cin>>mg[i].a>>mg[i].b>>mg[i].v;

    sort(mg+1,mg+m+1,kruskal_poredi);  // sortiramo grane rastuce po tezinama

    for(i=1;i<=n;i++) kruskal_roditelj[i]=i;

    cout<<"Grane koje pripadaju minimalnom pokrivajucem stablu su:"<<endl;
    int u=0;
    for(i=1;i<=m;i++)
    {
        x=kruskal_nadji(mg[i].a);  y=kruskal_nadji(mg[i].b);
        if(x!=y && u<n)
        {kruskal_spoj(x,y); u++; cout<<mg[i].a<<" "<<mg[i].b<<" "<<mg[i].v<<endl;  MPS_suma+=mg[i].v;}
    }
    cout<<"Suma vrednosti grana koje pripadaju MPS je "<<MPS_suma<<"."<<endl;
}

int rast[1005];
struct dij_cvor {int c,v;};
vector <dij_cvor> mg8[1005];
struct uredi
{
    bool operator()(const dij_cvor & l,const dij_cvor & d)
    {
        if(l.v>d.v) return 1;
        else return 0;
    }
};
priority_queue<dij_cvor,vector<dij_cvor>,uredi> pr;
void dijkstra()
{
  int n,m,i,j,k,s,a,b,x;
    dij_cvor novi,t;
    cout<<"Uneti redom broj cvorova, broj grana grafa i polazni cvor."<<endl;
    cout<<"Za svaku granu uneti cvorove koje povezuje, a zatim i njenu tezinu."<<endl;
    cin>>n>>m>>s;
    for(i=1;i<=m;i++)
    {
        cin>>a>>b>>t.v;
        t.c=b;  mg8[a].push_back(t);
        t.c=a;  mg8[b].push_back(t);
    }
    for(i=1;i<=n;i++) {marka[i]=0;  rast[i]=-1;}  //Oznaka za beskonacno je -1
    rast[s]=0;
    novi.c=s;  novi.v=0; pr.push(novi);

    int u=n;
    while(u--)
    {
      while(marka[pr.top().c]==1) pr.pop();

        t=pr.top(); marka[t.c]=1;

      for(i=0;i<mg8[t.c].size();i++)
       {
        x=mg8[t.c][i].c;
        if(marka[x]==1) continue;    //ukoliko grana povezuje trenutni cvor i neki vec markirani cvor
        if(rast[x]==-1 || rast[t.c]+mg8[t.c][i].v<rast[x])
        {rast[x]=rast[t.c]+mg8[t.c][i].v; novi.c=x;  novi.v=rast[x]; pr.push(novi);}
       }
    }

    cout<<"Duzine minimalnih puteva od cvora "<<s<<" do svih ostalih su redom:"<<endl;
    for(i=1;i<=n;i++) cout<<rast[i]<<" ";

}

void prikazi_meni()
{
    cout<<endl<<endl;
    cout<<"Za pokretanje nekog od algoritama uneti odgovarajuci broj."<<endl;
    cout<<"1 dfs"<<endl;
    cout<<"2 bfs"<<endl;
    cout<<"3 Topolosko sortiranje, algoritam zasnovan na dfs-u"<<endl;
    cout<<"4 Topolosko sortiranje, Kanov algoritam"<<endl;
    cout<<"5 Primov algoritam"<<endl;
    cout<<"6 Struktura disjunktnih skupova"<<endl;
    cout<<"7 Kruskalov algoritam"<<endl;
    cout<<"8 Dijkstrin algoritam"<<endl;
    cout<<"Napomena: Za detalje i objasnjenja pogledati komentare."<<endl;
    cout<<endl;
}


int main()
{
    ios::sync_with_stdio(false);
    int x;

    cout<<"Maturski rad"<<endl;
    cout<<"Algoritmi za resavanje problema iz teorije grafova"<<endl;
    prikazi_meni();

    while(cin>>x)
    {
        if(x==1) dfs();
        else if(x==2) bfs();
        else if(x==3) toposort_dfs();
        else if(x==4) toposort_kan();
        else if(x==5) primov_algoritam();
        else if(x==6) dsu();
        else if(x==7) kruskal();
        else if(x==8) dijkstra();

        prikazi_meni();
    }
    return 0;
}
