Skip to content
Programming101
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
Programming101
Programmingoneonone

HackerEarth Maximum size of a set problem solution

YASH PAL, 31 July 2024
In this HackerEarth Maximum size of a set problem solution You are given a DAG N with N nodes and M edges. You are building a graph G^. G^ contains the same vertex set as G and all edges are available in G. Moreover,
  1. If there exists an edge between vertex u and v in G, then there does not exist an edge between vertex v and u in G^.
  2. If there exists an edge between vertex u and v in G and also between v and w in G, then there exists an edge between vertex u and w in G^.
For G^, find the maximum possible size of S where S is a set of vertices in G^ such that there exists an edge between every unordered pair of vertex present in S.
The meaning of unordered is that there must exist an edge between every pair of vertex (u,v), that is, either u – > v or v – > u must be in an edge set.
HackerEarth Maximum size of a set problem solution

HackerEarth Maximum size of a set problem solution.

#include<bits/stdc++.h>
#define ll long long int
#define MAX 200005
using namespace std;
vector<int>adjacent[MAX];
int dp[MAX];
bool visited[MAX];

void dfs(int u)
{
visited[u] = true;

dp[u] = 1;
for(int i = 0 ; i < adjacent[u].size() ; i++)
{
int v = adjacent[u][i];

if(!visited[v])
{
dfs(v);
}

dp[u] = max(dp[u], 1 + dp[v]);
}
}

int main(){
int N, M;
cin>>N>>M;

assert(N <= 200000 && M <= 1000000);

for(int i = 1 ; i <= M ; i++)
{
int u , v;
cin >> u >> v;
adjacent[u].push_back(v);
}


for(int i = 1 ; i <= N ; i++)
{
if(!visited[i])
{
dfs(i);
}
}

int ans = -1;

for(int i = 1 ; i <= N ; i++)
{
ans = max(ans, dp[i]);
}

cout<<ans<<endl;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 14;
vector<int> g[maxn], ord;
int n, m, dp[maxn];
bool mark[maxn];
void dfs(int v){
if(mark[v])
return ;
mark[v] = true;
for(auto u : g[v])
dfs(u);
ord.push_back(v);
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
for(int i = 0; i < m; i++){
int v, u;
cin >> v >> u;
v--, u--;
g[v].push_back(u);
}
for(int i = 0; i < n; i++)
dfs(i);
for(auto v : ord){
dp[v] = 1;
for(auto u : g[v])
dp[v] = max(dp[v], dp[u] + 1);
}
cout << *max_element(dp, dp + n) << 'n';
}
coding problems solutions

Post navigation

Previous post
Next post

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