# Cod sursa(job #2448403)

Utilizator Data 16 august 2019 20:23:35 Radiatie 100 cpp-64 done Arhiva de probleme 1.95 kb
``````
#include<bits/stdc++.h>

using namespace std;

int n, m, k;

struct mch

{

int a, b, c;

};

mch v[30002];

bool cmp(mch a, mch b)

{

return a.c < b.c;

}

vector<int>dsu[15002];

int tt[15002], ttv[15002], sz[15002], pz1[15002], pz2[15002];

int ans[15002];

int Find(int nod)

{

if(tt[nod] == nod)

return nod;

return tt[nod] = Find(tt[nod]);

}

int Find2(int nod)

{

if(ttv[nod] == nod)

return ttv[nod];

return ttv[nod] = Find2(ttv[nod]);

}

int cost;

void Union(int a, int b)

{

int nnv = Find2(ttv[a]), nl = Find2(ttv[b]);

if(sz[a] >= sz[b])

tt[b] = a, sz[a] += sz[b];

else

tt[a] = b, sz[b] += sz[a];

if(dsu[nnv].size() < dsu[nl].size())

swap(nnv, nl);

for(int i = 0; i < dsu[nl].size(); ++i)

{

int val = dsu[nl][i];

if(Find2(pz1[val]) == nnv && Find2(pz2[val]) == nl)

ans[val] = cost;

else

if(Find2(pz1[val]) == nl && Find2(pz2[val]) == nnv)

ans[val] = cost;

else

dsu[nnv].push_back(val);

}

ttv[nl] = nnv;

}

int main()

{

f >> n >> m >> k;

for(int i = 1; i <= m; ++i)

f >> v[i].a >> v[i].b >> v[i].c;

sort(v+1, v+m+1, cmp);

for(int i = 1; i <= k; ++i)

{

int a, b;

f >> a >> b;

pz1[i] = a;

pz2[i] = b;

dsu[a].push_back(i);

dsu[b].push_back(i);

}

for(int i = 1; i <= n; ++i)

tt[i] = i, ttv[i] = i, sz[i] = 1;

for(int i = 1; i <= m; ++i)

{

cost = v[i].c;

if(Find(v[i].a) != Find(v[i].b))

Union(Find(v[i].a), Find(v[i].b));

}

for(int i = 1; i <= k; ++i)

g << ans[i] << '\n';

return 0;

}
``````