Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
  • Work with US
Programmingoneonone
Programmingoneonone

HackerEarth Components of Graph Airbus problem solution

YASH PAL, 31 July 2024
In this HackerEarth Components of Graph <Airbus> problem solution You are given a directed network of flights i.e. N cities and M one-directional flights. Each city has a particular air quality index value associated with it. Now, your task is to determine the maximum threshold value X such that if the flights incident to or from the cities with air quality index values less than X is canceled then there should exist a reachable component of cities in the network of size at least K. A subcomponent of a flight network is considered to be a reachable component if all the cities in that component are connected, this implies that all the flights are reachable from each other via direct or connecting flights.
HackerEarth Components of Graph <Airbus> problem solution

HackerEarth Components of Graph <Airbus> problem solution.

#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define endl "n"
#define eps 0.00000001
LL pow(LL a,LL b,LL m){ a%=m;LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
using namespace std;
int u[100001];
int v[100001];
int val[100001];
int n, m, k;
vector<int> graph[100001];
stack<int> scc_stack;
bool visit[100001];
int components_sz[100001];
int components_count = 0;
void dfs(int node) {
visit[node] = 1;
for(int i: graph[node]) {
if(visit[i] == 0) {
visit[i] = 1;
dfs(i);
}
}
scc_stack.push(node);
}


void dfs2(int node) {
components_sz[components_count]++;
visit[node] = 1;
for(int i: graph[node]) {
if(visit[i] == 1)
continue;
visit[i] = 1;
dfs2(i);
}
}

bool check(int limit) {
components_count = 0;
memset(visit, 0, sizeof(visit));
while(!scc_stack.empty()) {
scc_stack.pop();
}
for(int i = 1; i <= n; i++) {
graph[i].clear();
}
for(int i = 1; i <= m; i++) {
int a = u[i], b = v[i];
if(val[a] >= limit && val[b] >= limit) {
graph[a].push_back(b);
}
}
for(int i = 1; i <= n; i++) {
if(visit[i] == 0) {
dfs(i);
}
}
for(int i = 1; i <= n; i++)
graph[i].clear();
memset(visit, 0, sizeof(visit));
for(int i = 1; i <= m; i++) {
int a = u[i], b = v[i];
if(val[a] >= limit && val[b] >= limit) {
graph[b].push_back(a);
}
}
while(scc_stack.size()) {
int cur = scc_stack.top();
scc_stack.pop();
if(visit[cur] == 1)
continue;
++components_count;
dfs2(cur);
}
int ans = 0;
for(int i = 1; i <= components_count; i++) {
ans = max(ans , components_sz[i]);
components_sz[i] = 0;
}
components_count = 0;
if(ans >= k)
return 1;
else
return 0;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
assert(cin >> n >> m >> k);

for(int i = 1; i <= n; i++)
assert(cin >> val[i]);
for(int i = 1; i <= m; i++) {
assert(cin >> u[i] >> v[i]);
}
int l = 1, r = 1000000000;
int ans = -1;
while(l <= r) {
int mid = (l + r) / 2;
if(check(mid) == 1) {
ans = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
assert(ans != -1);
cout << ans << endl;
}
coding problems solutions

Post navigation

Previous post
Next post

Related website

The Computer Science

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes