How can we say this-"the no of edges are not too many"

problem link is: FIRESC Problem - CodeChef
and the statement which seems problematic to me is contained in the image attached. How can we say that are the no of edges not too many? As 1 can be friends with 2, 2 with 3 and so on…?

As per the question, N is no of vertices and M is no of edges. Both, N and M are <=10^5. It is always preferred to use adjacency list to store graph rather than adjacency matrix. If you create adjacency matrix, you require O(N*N) space, whereas adjacency list requires O(M) space. It is beneficial to look at constraints and then use one of this to store graph.

1 Like

i asked you why is it stated that the number of edges are not too many?

There are N vertices, so in a complete graph there can be N*(N-1)/2 edges which will be 10^10 in this question. But it is given that edges will be at max 10^5 which are not too many.

2 Likes

gotcha!