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

[Alan Gauld]

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