[Tutor] Fwd: Graph question was: Re: (no subject)
Alan Gauld
learn2program at gmail.com
Mon Mar 15 19:56:15 EDT 2021
Forwarding to the group....
-------- Forwarded Message --------
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.
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). 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. The output
of the program is: If kkrepresents a valid node, print all the nodes
sssuch that s→ks→kis a (directed) edge in the graph. The nodes have to
be in sorted order, separated by COMMA (no whitespace). If kkdoes not
represent a valid node, print "ERROR: Invalid Node." EXAMPLES
___________________________________ INPUT: 3 4 0,1 1,2 2,0 0,2 2 OUTPUT:
0,1 _____________________________ INPUT: 3 4 0,1 0,2 2,0 0,2 2 OUTPUT: 0
_____________________________ INPUT: 1 0 0 OUTPUT: (Note empty output)
_____________________________ NOTE: Remember that Self edges (i→ii→i)
are allowed. Multi-edges (two or more instances of i→ji→j) have to be
counted only once.
On Sun, Mar 14, 2021 at 8:28 PM Alan Gauld <learn2program at gmail.com
<mailto:learn2program at gmail.com>> wrote:
Please supply a relevant subject line, it makes tracking the discussion
much easier.
On 14/03/2021 12:39, ੧ wrote:
> Dear sir, I have not studies graph-related things in python.
Have you studied graphs in math?
Python is pretty much irrelevant since it does not directly
deal in graphs. You need to do that yourself.
ie. can you solve the problem below without Python?
If not then that is where you must start.
First understand the problem.
> The first line
> will contain a positive integer NN. NN denotes the number of nodes
in the
> graph. Nodes themselves are numbered from 0 to N−1N−1.
OK, This has lost me already. The number of nodes should
surely be N? Not NN? How are the nodes in a graph numbered
Can you provide an example? The input samples below do
not appear to match the description.
Can you repost the question with clearer formatting
and better examples?
The more you can help us the more we can help you.
> 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). The
> next MM lines each will contain a pair of integers i,ji,j
representing 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. The output of the program is: If kk
represents
> a valid node, print all the nodes ss such that s→ks→k is a
(directed) edge
> in the graph. The nodes have to be in sorted order, separated by
COMMA (no
> whitespace). If kk does not represent a valid node, print "ERROR:
Invalid
> Node." EXAMPLES ___________________________________ INPUT: 3 4 0,1
1,2 2,0
> 0,2 2 OUTPUT: 0,1 _____________________________ INPUT: 3 4 0,1 0,2
2,0 0,2
> 2 OUTPUT: 0 _____________________________ INPUT: 1 0 0 OUTPUT:
(Note empty
> output) _____________________________ NOTE: Remember that Self
edges (i→ii→i)
> are allowed. Multi-edges (two or more instances of i→ji→j) have to be
> counted only once.
--
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/ <http://www.alan-g.me.uk/>
http://www.amazon.com/author/alan_gauld
<http://www.amazon.com/author/alan_gauld>
Follow my photo-blog on Flickr at:
http://www.flickr.com/photos/alangauldphotos
<http://www.flickr.com/photos/alangauldphotos>
--
TaranSingh
More information about the Tutor
mailing list