How many countries?

Report a typo

In the universe of Algoria, there is a single rule for cities to be grouped into a country: there should be a path between every pair of such cities. The roads are one-way and traveling can be done only by using these roads. Here is the system of roads between all cities in Algoria:

D1 -> D2
D2 -> D3
D2 -> D5
D2 -> D6
D3 -> D4
D3 -> D7
D4 -> D3
D4 -> D8
D5 -> D1
D5 -> D6
D6 -> D7
D7 -> D6
D8 -> D4
D8 -> D7

Your task is to calculate the smallest number of countries that can be created in Algoria.

For example, D1D1, D2D2, and D5D5 could form a country, since there is a path between each pair of them. But that's not all: can this country get bigger? In other words, can we add more cities in it, as we need to find the smallest number of countries?

Hint: What is a "country" in this task in terms of graph theory? So, what are you asked to calculate?

Enter a number
___

Create a free account to access the full topic