Problem link: Hall Allocation - Problems - CodeChef
Auth: picramide
We are interested in forming a happy room such that the minimum cgpa of students of that room is maximum.
So first we sort the pairs of friends (u, v) in decreasing order of min(CG_u, CG_v). Now we add the edges in our graph upto when a connected component of size k is formed and then output the minimum CGPA of students in that connected component. If no component of size k is formed then no happy room can exist.
This can be achieved by using disjoint set union data structure.
C++ Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
const ll N = 200005;
ll n, m, k;
ll cg[N];
pair<ll, ll> adj[N];
int parent[N], sz[N], mn[N];
void make_set(int x){
parent[x] = x;
sz[x] = 1;
mn[x] = cg[x];
}
int find_set(int x){
if(x == parent[x]) return x;
return parent[x] = find_set(parent[x]);
}
void union_set(int a, int b){
a = find_set(a); b = find_set(b);
if(a == b) return;
if(sz[a] < sz[b]) swap(a,b);
parent[b] = a;
mn[a] = min(mn[a], mn[b]);
sz[a] += sz[b];
}
bool cmp(const pair<ll,ll> a, const pair<ll,ll> b){
return min(cg[a.fr], cg[a.sc]) > min(cg[b.fr], cg[b.sc]);
}
void solve(){
cin >> n >> m >> k;
for (ll i = 0; i < n; ++i){
cin >> cg[i + 1];
make_set(i + 1);
}
for (ll i = 0; i < m; ++i){
cin >> adj[i].fr >> adj[i].sc;
}
sort(adj, adj + m, cmp);
for (ll i = 0; i < m; ++i){
int a = find_set(adj[i].fr); int b = find_set(adj[i].sc);
union_set(a,b);
if(max(sz[a], sz[b]) >= k){
cout << min(mn[a], mn[b]);
return;
}
}
cout << -1;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tt = 1; cin >> tt;
while(tt--){
solve();
cout << endl;
}
return 0;
}