Циклы в графе. Двудольность: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) |
||
| Строка 22: | Строка 22: | ||
* [http://acmp.ru/?main=task&id_task=151 ACMP #151 — Банкет] | * [http://acmp.ru/?main=task&id_task=151 ACMP #151 — Банкет] | ||
* [http://acmp.ru/?main=task&id_task=152 ACMP #152 — Построение] | * [http://acmp.ru/?main=task&id_task=152 ACMP #152 — Построение] | ||
* [http://acm.timus.ru/problem.aspx?num=1080 Timus #1080 — Раскраска карты] | |||
== Ссылки == | == Ссылки == | ||
Версия от 15:12, 11 октября 2014
vector<int> g[V_CNT];
int u[V_CNT];
void dfs(int v) {
u[v] = 1;
for (int i = 0; i < g[v].size(); i++) {
if (u[g[v][i]] == 1)
/* граф содержит цикл */;
if (!u[g[v][i]])
dfs(g[v][i]);
}
u[v] = 2;
}
for (int i = 0; i < V_CNT; i++)
u[i] = 0;
for (int i = 0; i < V_CNT; i++)
if (!u[i])
dfs(i);