Consider a graph G having N vertices. For each vertex, I am given adjacency vector, denoting the elements adjacent to vertex in G.
For example say :-
N = 4, and adjacency matrix is like :
[1] = {3,4}
[2] = {3}
[3] = {1,2,4}
[4] = {1, 3}
What I am required to find is the number of connected components in the complement of G 
in say O(N) or O(Nlog(N)). I tried but my approach is O(N^2). I am applying dfs and iterating i from 1 to N and checking if i is not present in the adjaceny matrix of source vertex (in dfs) and then continuing DFS.
Similar Problem was asked in a contest yesterday. Problem link, Solution link.