Cod sursa(job #2691226)

Utilizator denisa.iordacheIordache Denisa-Elena denisa.iordache Data 27 decembrie 2020 16:57:37
Problema PScNv Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int NMAX = 250010;
const int MMAX = 50010;
int n,m,x,y,t[NMAX];
struct muchie
{
    int s, d, c;
} G[MMAX];

bool cmp ( muchie a, muchie b)
{
    return a.c < b.c;
}

int parent (int nod)  //functie pentru determinarea inceputului unei componente conexe
{
    while (t[nod]!=nod)
        nod = t[nod];
    return nod;

}

void union_N ( int nod1, int  nod2)
{
        t[nod2] = nod1;
}

int main() {
    ifstream f("pscnv.in");
    ofstream g("pscnv.out");
    f>>n>>m>>x>>y;
    for(int i=0;i<m;i++)
    {
        f>>G[i].s>>G[i].d>>G[i].c;
    }
    sort(G,G+m,cmp);

    for(int i = 1; i <=n; i++)
    {
        t[i] = i;
    }

    for(int i=0;i<m;i++) {
        int n1 = parent(G[i].s);
        int n2 = parent(G[i].d);

        if (n1 != n2) //daca nodurile nu fac parte din aceeasi componenta conexa
            union_N(n1, n2);
        if(parent(x) == parent(y))
        {
            g<<G[i].c;
            break;
        }


    }
    f.close();
    g.close();

    return 0;
}