Точки сочленения. Компоненты вершинной двусвязности: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Строка 1: Строка 1:
 +
* Для каждой вершины <tt>v</tt> будем подсчитывать время входа <tt>tIn[v]</tt> и величину <tt>tUp[v]</tt> &mdash; минимальное <tt>tIn</tt> для некоторой вершины, достижимой из текущего поддерева переходом по одному обратному ребру.
 +
* Вершина <tt>v</tt> является точкой сочленения, если из её поддерева в дереве обхода в глубину нет обратных рёбер в её предков (<tt>tUp[v] >= tIn[v]</tt>).
 +
* Корень дерева обхода в глубину (<tt>parent == -1</tt>) является точкой сочленения тогда и только тогда, когда у него более одного непосредственного потомка.
 +
 +
vector<int> g[V_CNT];
 +
bool u[V_CNT];
 +
int tIn[V_CNT], tUp[V_CNT], timer;
 +
 +
void dfs(int v, int parent = -1) {
 +
    u[v] = 1;
 +
    tUp[v] = tIn[v] = timer++;
 +
    int childrenCount = 0;
 +
    for (int i = 0; i < g[v].size(); i++) {
 +
        if (!u[g[v][i]]) {
 +
            dfs(g[v][i], v);
 +
            childrenCount++;
 +
            tUp[v] = min(tUp[v], tUp[g[v][i]]);
 +
        } else if (g[v][i] != parent)
 +
            tUp[v] = min(tUp[v], tIn[g[v][i]]);
 +
    }
 +
    if (tUp[v] >= tIn[v] || (parent == -1 && childrenCount > 1))
 +
        /* v - точка сочленения */;
 +
}
 +
 +
for (int i = 0; i < V_CNT; i++)
 +
    u[i] = tIn[i] = tUp[i] = 0;
 +
timer = 0;
 +
for (int i = 0; i < V_CNT; i++)
 +
    if (!u[i])
 +
        dfs(i);
 +
 
== Ссылки ==
 
== Ссылки ==
 
* [http://e-maxx.ru/algo/cutpoints e-maxx.ru &mdash; Поиск точек сочленения]
 
* [http://e-maxx.ru/algo/cutpoints e-maxx.ru &mdash; Поиск точек сочленения]

Версия 23:49, 1 октября 2014

  • Для каждой вершины v будем подсчитывать время входа tIn[v] и величину tUp[v] — минимальное tIn для некоторой вершины, достижимой из текущего поддерева переходом по одному обратному ребру.
  • Вершина v является точкой сочленения, если из её поддерева в дереве обхода в глубину нет обратных рёбер в её предков (tUp[v] >= tIn[v]).
  • Корень дерева обхода в глубину (parent == -1) является точкой сочленения тогда и только тогда, когда у него более одного непосредственного потомка.
vector<int> g[V_CNT];
bool u[V_CNT];
int tIn[V_CNT], tUp[V_CNT], timer; 

void dfs(int v, int parent = -1) {
    u[v] = 1;
    tUp[v] = tIn[v] = timer++;
    int childrenCount = 0;
    for (int i = 0; i < g[v].size(); i++) {
        if (!u[g[v][i]]) {
            dfs(g[v][i], v);
            childrenCount++;
            tUp[v] = min(tUp[v], tUp[g[v][i]]);
        } else if (g[v][i] != parent)
            tUp[v] = min(tUp[v], tIn[g[v][i]]);
    }
    if (tUp[v] >= tIn[v] || (parent == -1 && childrenCount > 1))
       /* v - точка сочленения */;
}

for (int i = 0; i < V_CNT; i++)
    u[i] = tIn[i] = tUp[i] = 0;
timer = 0;
for (int i = 0; i < V_CNT; i++)
    if (!u[i])
        dfs(i);

Ссылки