Oʻzbekiston respublikasi oliy ta’lim, fan va innovatsiyalar vazirligi mirzo ulug‘bek nomidagi milliy universitetininig jizzax filiali

Sikllar uchun grafikni tekshirish

Shuni ta'kidlash kerakki, bizdan barcha sikllarni topish talab qilinmaydi, biz faqat kamida bittasi bor yoki yo'qligiga javob berishimiz kerak. Barcha sikllarni topish muammosini hal qilish ancha qiyin.

Algoritm

Siklni qidirish uchun biz DFS dan foydalanamiz. Masalan, ushbu grafikni ko'rib chiqing:

Aytaylik, biz DFSni 1-tugundan boshladik va u grafikni butunlay chetlab o'tdi. Keling, ushbu grafikning o'tishini daraxtlarni tasvirlaganimizdek, rekursiya chuqurligiga qarab
darajalar bo'yicha tasvirlaymiz:

(Eslatma: bu mumkin bo'lgan chuqurlikdagi birinchi qadamlardan biri.)

Ko'rib turganingizdek, siklga kiritilgan qirralarning birida DFS pastga tushmadi: u qizil rang bilan ta'kidlangan. Grafikda shunday "ko'tarilgan" qirralarning mavjudligi tufayli unda sikllar mavjudligini aniqlash mumkin. DFSni amalga oshirishda bunday qirralarni aniqlash oson: ular allaqachon tashrif buyurilgan (!used[i]) tepada, lekin to'g'ridan-to'g'ri ajdodda emas (dfs(i)).

Amalga oshirish

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

#include using namespace std; vector graph[100000]; bool used[100000]; void dfs(int v, int p = -1) { //p - прямой предок used[v] = true; for (int u: graph[v]) { if (!used[u]) { dfs(u, v); } else if (u != p) { cout << "Graph has cycles."; exit(0); //Полностью выйти из программы. } } } int main() { //Ввод графа... //Проверяем отдельно каждую вершину, так как //граф может быть несвязным, но всё равно иметь циклы for (int i = 0; i < n; i++) { if (!used[i]) { dfs(i); } } //Если мы ещё не вышли не вышли из программы, в графе нет циклов. cout << "Graph has no cycles."; }

Murakkablik: O(N)