[Tutor] Fwd: Graph question was: Re: (no subject)

[Alan Gauld]

On 15/03/2021 23:56, Alan Gauld wrote:

> I have written it in a more readable format.
> In this problem, you need to create a program for managing Graphs. The
> input to the program will be as described next: The first line will
> contain a positive integer NN. NNdenotes the number of nodes in the
> graph. Nodes themselves are numbered from 0 to N−1N−1.

I'm probably just being dense but I still don't understand this.

It says the number is NN which denotes the number of nodes.
I'd read that as a two digit number.

Then it says it ranges from 0 to N-1
That suggests to me that the number of nodes should really
read the index of the highest node? Maybe? Except...

It says "numbered from 0 to N-1N-1" which suggests that if
N is, say, 5 the numbering could be up to 44?
Which makes no sense to me at all!

>  The second line will contain a non-negative integer MM(M≥0M≥0). This
> will be the number of edges in the graph (However, some of these could
> be invalid/duplicate). 

This has a similar issue in that how is a single number of edges
represented using a double digit?

And when we look at the sample data below the first
two "lines" are both single digits...

> The next MMlines each will contain a pair of
> integers i,ji,jrepresenting a directed edge i→ji→j. Self edges (i→ii→i)
> are allowed. However, multi-edges (two or more instances of i→ji→j) have
> to be stored only once. Last line will contain an integer kk. 

And what is kk supposed to be? There is no explanation.

>  If kkrepresents a valid node, print all the nodes
> sssuch that s→ks→kis a (directed) edge in the graph. 

OK, Now we have a sort of explanation for kk - it might be a node.
but we introduce a new term s. What is s?

> ___________________________________ INPUT: 3 4 0,1 1,2 2,0 0,2 2 OUTPUT:
> 0,1 

I assume this should be written:

3
4
0,1
1,2
2,0
0,2
2

ie 3 nodes, 4 edges and the mystery node is 2.
The solution is apparently 0,1 but I'm not sure why?

As I say, it's probably me missing something (and my
graph theory days are long behind me so that's very
likely!)

But unless we understand what the data represents
and how the output should be calculated we can't
begin to discuss what the Python code might look
like.

-- 
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.amazon.com/author/alan_gauld
Follow my photo-blog on Flickr at:
http://www.flickr.com/photos/alangauldphotos