Циклы в графе. Двудольность: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (→Ссылки) |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
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); | |||
== Ссылки на задачи == | == Ссылки на задачи == | ||
* [http://acmp.ru/?main=task&id_task=151 ACMP #151 — Банкет] | * [http://acmp.ru/?main=task&id_task=151 ACMP #151 — Банкет] | ||
Версия от 19:01, 1 октября 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);