HackerEarth Maximum size of a set problem solution

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,

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^.
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.

#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