https://svn.boost.org/trac10/ticket/10222 <p> I think in boost::graph strong_components does not compute the root map as claimed in the documentation, i.e., that it maps each vertex to the root of the corresponding scc. </p> <p> For a counter-example consider the following graph (attached as a MWE): </p> <blockquote> <p> a &lt;-&gt; b &lt;-&gt; c </p> </blockquote> <p> Suppose the algorithm starts with node a. The protocol of the algorithm is as follows, the first column being the discovery time, the second being the content of the root map, and * indicating uninitialized values: </p> <p> 1) a -&gt; (0, a), b -&gt; (*, *), c -&gt; (*, *) <em> discovered a </em></p> <p> 2) a -&gt; (0, a), b -&gt; (1, b), c -&gt; (*, *) <em> discovered b </em></p> <p> 3) a -&gt; (0, a), b -&gt; (1, b), c -&gt; (2, c) <em> discovered c </em></p> <p> 4) a -&gt; (0, a), b -&gt; (1, b), c -&gt; (1, b) <em> finished c </em></p> <p> 5) a -&gt; (0, a), b -&gt; (0, b), c -&gt; (1, b) <em> finished b </em></p> <p> 6) a -&gt; (0, a), b -&gt; (0, a), c -&gt; (1, b) <em> finished a </em></p> <p> The value of the root map for c is 1, correct would be 0. </p> <p> The output of the example is as follows:<br /> The example graph:<br /> a --&gt; b <br /> b --&gt; a c <br /> c --&gt; b <br /> <br /> Vertex a is in component 0 and has root 0<br /> Vertex b is in component 0 and has root 0<br /> Vertex c is in component 0 and has root 1<br /> </p> en-us /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/10222 Trac 1.4.3 Alex <alxlaus@…> Mon, 21 Jul 2014 19:53:12 GMT https://svn.boost.org/trac10/ticket/10222 https://svn.boost.org/trac10/ticket/10222 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">rootmap_bug.cpp</span> </li> </ul> <p> MWE </p> Ticket Alex <alxlaus@…> Mon, 21 Jul 2014 19:54:24 GMT https://svn.boost.org/trac10/ticket/10222 https://svn.boost.org/trac10/ticket/10222 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">rootmap_bug.2.cpp</span> </li> </ul> Ticket Alex <alxlaus@…> Mon, 21 Jul 2014 19:56:11 GMT https://svn.boost.org/trac10/ticket/10222#comment:1 https://svn.boost.org/trac10/ticket/10222#comment:1 <ul> <li><strong>cc</strong> <span class="trac-author">alxlaus@…</span> added </li> </ul> Ticket Alex <alxlaus@…> Wed, 23 Jul 2014 11:16:22 GMT