ROME Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Kanhaiya Mohan
Tester: Felipe Mota, Aryan
Editorialist: Pratiyush Mishra

DIFFICULTY:

2676

PREREQUISITES:

Graphs

PROBLEM:

The country of Chefland is a group of N cities having M directed roads between its cities. It takes 1 second to travel on any road.

Chef has decided to travel through this country. His travel plan goes as follows -

  • He will randomly choose a starting city.
  • While there are outgoing roads in his current city, he will randomly choose one of them and travel it. He can choose roads he has already traveled through and visit cities multiple times.
  • He will stop if there are no outgoing roads in the current city or N seconds have passed.

Chef will be disappointed if after traveling he does not end up in the capital city.

The ministers have not yet decided upon the capital city. They would like to choose it in such a way that Chef is not disappointed by his trip. To make their decision a bit easier, they can build some new roads between cities.

Find the minimum number of roads that need to be built such that the ministers can choose a capital city that doesn’t disappoint Chef no matter where his trip starts or how it progresses.

It is possible that the current road system is such that no matter which roads are added, a capital that doesn’t disappoint Chef cannot be chosen. In this case, print -1 instead.

QUICK EXPLANATION:

Observation \;1: The candidates that can be a capital city cannot have any outgoing edges.
Observation \;2: If the graph contains any cycle, then there cannot be a capital city.

Claim For any k candidates for capital cities, the number of edges that needs to be added to make a unique capital is (k-1)

Thus we would first check for cycles in the graph and if no cycle is present in the graph, then we would count the number of vertices having no outgoing edges and answer would be one less than that.

TIME COMPLEXITY:

O(V + E) for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester-1’s Solution
Tester-2’s Solution

1 Like

But i think there is one more case when capital city is not possible

when there is a edge between A->B and B->A

please correct me if i am wrong

yaa for that case the answer is -1 and it is already given in the sample test cases also.

This is equivalent to a cycle of size 2 and we’ve checked for cycles already.

1 Like