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

[Roel Schroeven]

Alan Gauld via Tutor schreef op 16/03/2021 om 1:34:
> On 15/03/2021 23:56, Alan Gauld wrote:

> 
> 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.

That is indeed almost certainly the case. IIRC problems on HackerRank, 
and possibly other sites like it, use an input format like that.

> The solution is apparently 0,1 but I'm not sure why?

I think I understand it. We have a set of directed edges i -> j. Then we 
are given a node k, find all edges that go towards that node k, and 
finally enumerate all starting nodes of those edges.

In the example, we have 4 edges:
- 0 -> 1
- 1 -> 2
- 2 -> 0
- 0 -> 2
We are asked to find all edges that end in 2 (because k is given as 2). 
Those are:
- 1 -> 2
- 0 -> 2
The starting nodes therefore are 1 and 0 (or 0 and 1; it looks like the 
order doesn't matter).

Or in code: [s for (s, j) in edges if j == k]

-- 
"Honest criticism is hard to take, particularly from a relative, a
friend, an acquaintance, or a stranger."
         -- Franklin P. Jones

Roel Schroeven