Algorithms and Data Structures

Check if the Graph is Efficient

Given an undirected graph with v vertices and e edges, you are asked to check if it’s efficient. A graph is considered efficient if it is possible to travel from any node to any other node by traversing at most 2 edges.


The first line of the input contains two integers v (1 ≤ v ≤ 100) and e (1 ≤ e ≤ 10 000).
The following e lines contain pairs of integers v1, v2 (1 ≤ v1, v2 ≤ v) representing an edge between v1 and v2.


The program should print Yes if the graph is efficient, and No otherwise.


4 3 1 2 2 3 3 1
4 4 1 2 2 3 3 1 1 4


  1. Vertex 4 is not connected to the others ⇒ it’s not possible to get from vertex 4 to any other by traversing at most 2 edges.
  1. It’s possible to get to any vertex from any other vertex by traversing at most 2 edges.


Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue