https://wiki.universitas.ro/index.php?action=history&feed=atom&title=2282_-_Componente_Conexe_4 2026-05-01T06:36:13Z Revision history for this page on the wiki MediaWiki 1.42.1 https://wiki.universitas.ro/index.php?title=2282_-_Componente_Conexe_4&diff=7979&oldid=prev 2023-12-13T12:10:15Z

<p>Pagină nouă: == Enunț == Se consideră un graf neorientat cu &lt;code&gt;n&lt;/code&gt; vârfuri și &lt;code&gt;m&lt;/code&gt; muchii. Cele &lt;code&gt;m&lt;/code&gt; muchii se elimină pe rând din graf. = Cerința = Pentru fiecare muchie eliminată trebuie să spuneți câte componente conexe are graful. = Date de intrare = Programul citește de la tastatură numerele &lt;code&gt;n&lt;/code&gt; și &lt;code&gt;m&lt;/code&gt;, iar pe următoarele &lt;code&gt;m&lt;/code&gt; linii se află câte două valori &lt;code&gt;x&lt;/code&gt; și &lt;code&gt;y&lt;/code&gt; separate prin...</p> <p><b>New page</b></p><div>== Enunț ==<br /> Se consideră un graf neorientat cu &lt;code&gt;n&lt;/code&gt; vârfuri și &lt;code&gt;m&lt;/code&gt; muchii. Cele &lt;code&gt;m&lt;/code&gt; muchii se elimină pe rând din graf.<br /> <br /> = Cerința =<br /> Pentru fiecare muchie eliminată trebuie să spuneți câte componente conexe are graful.<br /> <br /> = Date de intrare =<br /> Programul citește de la tastatură numerele &lt;code&gt;n&lt;/code&gt; și &lt;code&gt;m&lt;/code&gt;, iar pe următoarele &lt;code&gt;m&lt;/code&gt; linii se află câte două valori &lt;code&gt;x&lt;/code&gt; și &lt;code&gt;y&lt;/code&gt; separate prin spațiu, reprezentând o muchie din graf. Muchiile vi se dau în ordinea în care ele se elimină din graf.<br /> <br /> = Date de ieșire =<br /> Programul va afișa pe ecran exact &lt;code&gt;m&lt;/code&gt; linii, pe fiecare linie &lt;code&gt;i&lt;/code&gt; aflându-se un singur număr natural reprezentând numărul componentelor conexe din graf după eliminarea celei de-a &lt;code&gt;i&lt;/code&gt;-a muchii.<br /> <br /> = Restricții și precizări =<br /> <br /> * &lt;code&gt;1 ≤ n ≤ 100 000&lt;/code&gt;<br /> * &lt;code&gt;1 ≤ m ≤ 500 000&lt;/code&gt;<br /> * Între două vârfuri va exista cel mult o muchie<br /> <br /> = Exemplul 1 =<br /> Intrare<br /> 5 6<br /> 1 2<br /> 3 4<br /> 2 3<br /> 1 5<br /> 5 4<br /> 4 1<br /> Ieșire<br /> 1<br /> 2<br /> 3<br /> 3<br /> 4<br /> 5<br /> <br /> === Explicație ===<br /> Sunt &lt;code&gt;5&lt;/code&gt; vârfuri și &lt;code&gt;6&lt;/code&gt; muchii. Urmează cele &lt;code&gt;6&lt;/code&gt; muchii în ordinea eliminării lor. După eliminarea muchiei &lt;code&gt;1 2&lt;/code&gt; graful este tot conex, deci rezultatul este &lt;code&gt;1&lt;/code&gt;. După eliminarea muchiei &lt;code&gt;3 4&lt;/code&gt; se obțin două componente conexe, una formată din vârfurile &lt;code&gt;2&lt;/code&gt;, &lt;code&gt;3&lt;/code&gt;, iar cealaltă componentă formată din vârfurile &lt;code&gt;1&lt;/code&gt;, &lt;code&gt;4&lt;/code&gt;, &lt;code&gt;5&lt;/code&gt;. Restul eliminărilor nu mai trebuie explicate că ați înțeles deja.<br /> <br /> == Exemplul 1 ==<br /> Intrare<br /> 1000000000 10000000000<br /> consola<br /> Datele nu corespund restrictiilor impuse</div>

Simina