Cod sursa(job #2845409)

Utilizator rares89_Dumitriu Rares rares89_ Data 7 februarie 2022 19:38:56
Problema Radiatie Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <bitset>
 
using namespace std;
 
ifstream fin("radiatie.in");
ofstream fout("radiatie.out");
 
struct krusk {
    int x, y, c;
};
 
bool cmp(krusk a, krusk b) {
    return a.c < b.c;
}
 
vector<krusk> v;
int n, m, k, T[15005], rg[15005], c[15005], niv[15005], root;
vector<int> G[15005];
bitset<15005> V;
 
void Union(int a, int b, int cost) {
    if(rg[a] < rg[b]) {
        T[a] = T[b];
        G[a].push_back(b);
        c[a] = cost;
        root = a;
    } else {
        T[b] = T[a];
        G[b].push_back(a);
        c[b] = cost;
        root = b;
    }
    if(rg[a] == rg[b]) {
        rg[a]++;
    }
}
 
int Find(int nod) {
    int x = nod;
    while(x != T[x]) {
        x = T[x];
    }
    while(nod != T[nod]) {
        int temp = T[nod];
        T[nod] = x;
        nod = temp;
    }
    return nod;
}
 
void dfs(int nod) {
    V[nod] = true;
    for(auto it : G[nod]) {
        if(!V[it]) {
            niv[it] = niv[nod] + 1;
            dfs(it);
        }
    }
}
 
int main() {
    fin >> n >> m >> k;
    for(int i = 0; i < m; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        v.push_back({x, y, c});
    }
    sort(v.begin(), v.end(), cmp);
    for(int i = 1; i <= n; i++) {
        T[i] = i;
        rg[i] = 1;
    }
    for(int i = 0; i < m; i++) {
        int nod1 = Find(v[i].x);
        int nod2 = Find(v[i].y);
        if(nod1 != nod2) {
            Union(nod1, nod2, v[i].c);
        }
    }
    niv[root] = 1;
    dfs(root);
    for(int i = 1; i <= k; i++) {
        int x, y;
        fin >> x >> y;
        int maxim = 0;
        while(x != y) {
            maxim = max(maxim, max(c[x], c[y]));
            x = T[x], y = T[y];
        }
        fout << maxim << "\n";
    }
    return 0;
}