Ёфтани ҷузъҳои пайвастшуда

Ёфтани ҷузъҳои пайвастшуда

Шарт

Графи ғайрисамтдор $G$ бо $n$ қулла ва $m$ канор дода шудааст. Талаб мешавад, ки дар он ҳамаи ҷузъҳои пайваст — гурӯҳҳои қуллаҳоеро ёфт, ки дар дохили гурӯҳ аз ҳар қулла ба ҳар қуллаи дигар расидан мумкин аст, ва байни гурӯҳҳои гуногун роҳ вуҷуд надорад.

Ҳал

Барои ҳал кардани ин масъала метавон DFS ё BFS-ро истифода бурд.

Дар асл мо як силсила оғозҳои DFS/BFS-ро иҷро мекунем:

• оғозии аввал аз қуллаи аввал сар мешавад ва ҳамаи қуллаҳои ҷузъи пайвасти аввалро меёбад;
• баъд қуллаи аввалини ҳанӯз боздиднашударо мегирем ва аз он гузаришро оғоз мекунем — ҳамин тавр ҷузъи дуюмро меёбем;
• ва ҳамин тавр идома медиҳем, то ҳамаи қуллаҳо боздид шаванд.

Вақти умумии кори алгоритм: $O(n + m)$.