Talk:Tarjan: Difference between revisions

← Older edit

Talk:Tarjan (view source)

Revision as of 22:35, 15 May 2023

1,231 bytes added , 1 year ago

→‎Task description: new section

Rdm

6,962

edits

Revision as of 08:20, 9 March 2020 (view source) Wherrera (talk \| contribs) m (→‎Correctness?) ← Older edit		Latest revision as of 22:35, 15 May 2023 (view source) Rdm (talk \| contribs) (→‎Task description: new section)
(3 intermediate revisions by 2 users not shown)
Line 12: 0</pre> Any thoughts? --[[User:Ledrug\|Ledrug]] ([[User talk:Ledrug\|talk]]) 08:37, 9 March 2020 (UTC) ~~Any thoughts?~~ Perhaps the task description needs better detail. ~~The~~Note ~~code~~that the examples ~~work~~never ifshow ~~all~~reciprocal ~~points~~connections ~~are~~-- ~~those~~if ofthere is a ~~digraph so 0~~2 => 14, ~~means that 0 is~~ we never see 4 => 2 listed in the data, ~~-- it's~~for asome ~~digraph.~~reason?▼ ~~connected to 1 the same way as 1 is to 0. Note that the examples never show reciprocal connections -- if there is a 2 => 4, we never~~ ▲ see 4 => 2 listed in the data -- it's a digraph. --[[User:Wherrera\|Wherrera]] ([[User talk:Wherrera\|talk]]) 08:19, 9 March 2020 (UTC) That can't be right. "Strongly connected" means between two nodes A and B, there is a path from A to B and there is a path from B to A, which only makes sense if edges are directed. If all connections are bidirectional, there is no difference between "connected" and "strongly connected", and the algorithm only needs a depth-first traversal without much of the bookkeeping at all. --[[User:Ledrug\|Ledrug]] ([[User talk:Ledrug\|talk]]) 08:37, 9 March 2020 (UTC) EDIE: Never mind: a node not strongly connected to anything else is considered to form its own component, so the above output is correct. Silly me. --[[User:Ledrug\|Ledrug]] ([[User talk:Ledrug\|talk]]) 09:28, 9 March 2020 (UTC) Ah, you mean that [[0], [1]] and [0, 1] are different answers. I see. I guess that the lack of any reciprocal connections is just the way the examples are written then. I'll correct my response. --[[User:Wherrera\|Wherrera]] ([[User talk:Wherrera\|talk]]) 09:36, 9 March 2020 (UTC) == Task description == We should really be putting more effort into readable and complete task descriptions. I know wikipedia is unlikely to go away, and is fairly stable, but task description by reference is still a bad habit to fall into. --[[User:Rdm\|Rdm]] ([[User talk:Rdm\|talk]]) 22:35, 15 May 2023 (UTC)