دقت کنید گراف داده شده در صورت سؤال، گرافی است که از چند دور مجزّا یال و تعدادی رأس که بواسطه‌ی چند یال به‌یکدیگر متّصل شده‌اند، تشکیل شده‌است. یک گراف جدید از روی گراف داده‌شده در صورت سؤال به شکل مقابل می‌سازیم: « به ازای هر مؤلفه ی دوهمبند یالی (مؤلفه‌ی دوهمبندی که رأس برشی ندارد)، یک رأس در گراف جدید می‌گذاریم. همچنین به ازای هر یک از رئوس برشی‌ یک رأس می‌گذاریم و آن را به رئوس متناظر با مولفه هایی که در آن قرار دارد متصل می‌کنیم. سپس در گراف جدید (که‌یک‌ درخت است) DFS می‌زنیم. می‌خواهیم در حین انجام این DFS، مسئله را حل کنیم. زیر درخت رأس $v$ درگراف جدید را در نظر بگیرید (بدون احتساب رأس ($v$. اگر مجموعه‌ای از رئوس گراف سابق که در گراف جدید در این زیردرخت قرار دارند شامل $x$ عضو باشد، در صورت وجود جواب حتما $\lfloor x/(n/k)\rfloor n/k$ تا از آن‌ها با هم‌تشکیل $\lfloor x/(n/k)\rfloor$ مؤلّفه‌ی $n/k$ رأسی داده و $x \mod n/k$ تای آن‌ها بواسطه‌ی رأس $v$ با رئوس بالایی‌مؤلّفه‌ی $n/k$ تایی تشکیل داده اند. پس کافیست برای رئوسی که فرزند $v$ هستند مسئله را حل کرده و ببینیم از هر‌‌‌‌‌‌‌‌‌‌‌‌کدام از فرزندان رأس $v$ چند رأس با بالا تشکیل مؤلّفه داده‌اند و سپس در دو حالت زیر مسئله را برای $v$ حل کنیم:

1. مولفه‌ی $v$ در گراف اصلی تنها شامل یک رأس باشد و دور نباشد؛ در این‌صورت اگر جمع رئوس باقی‌مانده از فرزندان دقیقاَ برابر $n/k-1$ باشد، مجموعه رئوس باقی‌مانده به همراه رأس $v$ یک مؤلّفه تشکیل می‌دهند (حتماَ در هر جواب این امر صادق است). اگر این تعداد از $n/k-1$ بیشتر شود، حتماَ هیچ جوابی وجود ندارد و عبارت -1 در خروجی چاپ می‌شود. درصورتی‌که این مقدار از $n/k-1$ کم‌تر شود، تعداد این رئوس به‌علاوه‌ی یک (خود رأس $v$)، به‌عنوان رئوس باقی‌مانده از این زیر درخت که حتماَ باید با پدر $v$ تشکیل مؤلّفه دهند، به پدر $v$ ارسال می‌شود. (طی روند بازگشتی DFS؛)
2. مؤلّفه‌ی متناظر با رأس $v$ در گراف اصلی تک رأسی نباشد؛ دراین‌صورت این مؤلّفه در گراف اصلی حتما یک دور است. در این مرحله به شکلی مانند شکل زیر رسیده‌ایم که در آن رأس $v_i$ به همراه رئوسی که از فرزندانش باقی‌مانده دارای $c_i$ رأس است.

باید تحقیق کنیم که آیا می‌توان این رئوس را به تعدادی دسته با اعضای متوالی، دسته‌بندی کرد که هر دسته جز دسته‌ی شامل $v_1$ دارای دقیقاَ $n/k$ رأس باشد یا نه (تعداد رئوس باقی‌مانده به همراه $v_1$ به پدر رأس فعلی فرستاده می‌شوند). دقّت کنید درصورتی‌که این کار امکان‌پذیر نباشد، حتماَ جواب نداریم و باید 1- را در خروجی چاپ کنیم. در واقع می‌خواهیم تعدادی فلش به شکل زیر روی آرایه‌ی $c$ به طول $l$ بگذاریم که مجموع اعداد نوشته شده بین فلش‌های $c_i$ و $c_{i+1}$ $1 \leq i \leq l-1$ برابر $n/k$ و مجموع اعداد قبل $c_1$ و بعد $c_n$ کم‌تر یا مساوی $n/k$ شود.

برای این کار ابتدا فلش اوّل را قبل از $c_1$ گذاشته آنقدر جلو می‌رویم تا برای اوّلین بار مجموع اعداد بین $c_1$ و $c_i$ از $n/k$ بیش‌تر شود. فلش دوم را پشت $c_i$ می‌گذاریم. فلش سوم را نیز پشت اوّلین $c_j$ می‌گذاریم که مجموع اعداد بین $c_i$ و $c_j$ از $n/k$ بیش‌تر شود. بدین ترتیب در پایان به‌یک فلش گذاری می‌رسیم. اگر این فلش گذاری شرایط خواسته شده را داشته باشد که مسئله حلّ است. اگر نه، قطعاَ جای فلش اوّل نادرست بوده لذا آن را یک واحد جلو برده و پس از آن به‌ترتیب برای $2 \leq i \leq l$ فلش $i$ ام را تا جایی جلو می‌بریم که جمع اعداد بین فلش $i-1$ ام و فلش $i$ ام از $n/k$ تجاوز نکند. اگر به جواب رسیدیم، مسئله حل است. درغیراین‌صورت باز فلش اوّل را جلو می‌بریم و جای بقیه فلش ها را تصحیح می‌کنیم. این کار را آنقدر تکرار می‌کنیم تا مجموع اعداد قبل از فلش اوّل بیش‌تر از $n/k$ شود. اگر جوابی یافتیم مسئله حلّ است و در غیر این‌صورت مسئله حل ندارد و -1 را در خروجی چاپ می‌کنیم. پیچیدگی زمانی حل این زیر مسئله از $O(l)$ است زیرا اگر $h$ فلش داشته باشیم، تا پایان این مراحل، هر فلش حداکثر تا مکان اوّلیه‌ی فلش جلویی‌اش جلو می‌رود.بنابرین درنهایت حداکثر $O(l)$ عملیات انجام می‌شود.

پیچیدگی

اگر رأسی که روی آن DFS می‌زنیم متناظر یک رأس در گراف اصلی باشد، در هر مرحله از اردر تعداد فرزندان $v$ عملیات انجام می‌شود. اگر هم این رأس متناظر یک دور شود، عملیات ما از اردر تعداد رئوس دور متناظر با آن است. لذا کل الگوریتم از $O(n)$ می‌باشد.