kruskal

#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<functional>
#include<algorithm>
using namespace std;
typedef pair<int, int> p;
priority_queue<pair<int, p>, vector<pair<int, p>>, greater<pair<int, p>>> g;
vector <p> T;
vector <int> C1, C2;  //C1 will contain always the first node,and C2 the second
vector<int> C;
int n, m;
void read()
{
    ifstream in("file.txt");
    if (in.is_open())
    {
        in >> n >> m;
        int x, y, w;
        for (int i = 0; i<m; i++)
        {
            in >> x >> y >> w;
            g.push({ w,{ x,y } });
        }

    }
    else
        cout << "unable to open the file\n";
}
vector<int> find_(int val, vector<int> vect)
{
    //find all the positions
    vector<int> all;
    for (int i = 0; i < vect.size(); i++)
        if (val == vect[i])
            all.push_back(i);
    return all;
}
int form_cicle(vector<int> C1, vector<int> C2)
{
    int i = 0, j = 0;
    vector<int> one;
    for (int i = 0; i < C1.size(); i++)
        one.push_back(C1[i]);
    one.push_back(C2[i]);
    int start_ = one[one.size() - 2], end_ = one[one.size() - 1];
    one.pop_back();
    one.pop_back();
    int finish = 0, pos;
    vector<int> positions;
    while (!finish)
    {
        positions = find_(end_, one);
        if (positions.size() == 0)
            return 0;
        while (positions.size() != 0)
        {
            pos = positions[positions.size() - 1];
            positions.pop_back();
            one.erase(one.begin() + pos);
            if (pos % 2 == 1)
            {
                end_ = one[pos - 1];
                one.erase(one.begin() + pos - 1);
            }
            else
            {
                end_ = one[pos];
                one.erase(one.begin() + pos);

            }
            if (end_ == start_)
                return 1;
        }
    }

}


void kruskal()
{
    while (T.size()<n - 1)
    {
        pair<int, p> eliminated = g.top();
        g.pop();
        pair<int, int> edge = eliminated.second;

        C1.push_back(edge.first);
        C2.push_back(edge.second);
        cout << edge.first << " " << edge.second << endl;
        if (form_cicle(C1, C2) == 0)
        {
            T.push_back({ edge.second,edge.first });
            C1.push_back(C2[0]);
            C2.clear();
        }
        else
        {
            C1.pop_back();
            C2.pop_back();
        }
    }
}
int main()
{
    read();
    kruskal();
    cout << "MST:\n";
    for (int i = 0; i<T.size(); i++)
        cout << T[i].first << " " << T[i].second << endl;
    return 0;
}



/*
7 11
1 2 7
1 7 5
2 3 8
2 4 7
2 7 9
3 4 5
4 5 9
4 6 8
4 7 15
5 6 11
6 7 6


raspunsu should be 1 7,1 2, 4 2,4 3,4 5,7 6

*/