Maximum size of a set

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.

Example:

Input:
3 2
1 2
2 3
Output:
3

Approach

Java

import java.util.ArrayList;

public class MaximumSizeOfSet {
    public static void main(String args[]) {
        int n = 3;
        int m = 2, i;
        Graph g = new Graph(n);
        ArrayList<Integer> gr[] = new ArrayList[n + 1];
        for (i = 0; i <= n; i++)
            gr[i] = new ArrayList<>();

        int arr[][] = { { 1, 2 }, { 2, 3 } };
        for (i = 0; i < m; i++) {
            int l = arr[i][0];
            int r = arr[i][1];
            if (l == r || gr[l].contains(r))
                continue;
            if (l == r - 1 || r == l - 1)
                gr[l].add(r);
            g.addEdge(l, r);
        }
        int f = 1;
        if (n == 1)
            f = 0;
        for (i = 2; i <= n; i++)
            if (!(gr[i].contains(i - 1) || gr[i - 1].contains(i)))
                break;
        if (i > n)
            f = 0;
        if (f == 0)
            System.out.print(n);
        else
            System.out.print(g.findLongestPath(n) + 1);
    }

    static class Graph {

        int vertices;
        ArrayList<Integer> edge[];

        Graph(int vertices) {
            this.vertices = vertices;
            edge = new ArrayList[vertices + 1];
            for (int i = 0; i <= vertices; i++)
                edge[i] = new ArrayList<>();
        }

        void addEdge(int a, int b) {
            edge[a].add(b);
        }

        void dfs(int node, ArrayList<Integer> adj[], int dp[], boolean visited[]) {
            visited[node] = true;
            for (int i = 0; i < adj[node].size(); i++) {
                if (!visited[adj[node].get(i)])
                    dfs(adj[node].get(i), adj, dp, visited);
                dp[node] = Math.max(dp[node], 1 + dp[adj[node].get(i)]);
            }
        }

        int findLongestPath(int n) {
            ArrayList<Integer> adj[] = edge;
            int dp[] = new int[n + 1], i, ans = 0;
            boolean[] visited = new boolean[n + 1];

            for (i = 1; i <= n; i++)
                if (!visited[i])
                    dfs(i, adj, dp, visited);
            for (i = 1; i <= n; i++)
                ans = Math.max(ans, dp[i]);
            return ans;
        }
    }
}