kz-maxx

RU KZ
← Басты бет

Мосттар және articulation points

DFS, tin, low, bridge, cut point, неориентированный граф

Мост деген не?

Мост — неориентированный графтағы ребро. Егер осы реброны алып тастасақ, графтағы компоненттер саны көбейеді.

Жеңіл түсіндірме:

бір реброны өшіреміз
егер граф бірнеше бөлікке бөлініп кетсе
онда бұл ребро — мост

Мысалы:

1 -- 2 -- 3
2--3 ребросы мост болады

Точка сочленения деген не?

Точка сочленения немесе articulation point — графтағы вершина. Егер осы вершинасын алып тастасақ, компоненттер саны көбейеді.

Жеңіл түсіндірме:

бір вершина өшіріледі
егер граф бірнеше бөлікке бөлінсе
онда бұл вершина — точка сочленения

Мысалы:

1 -- 2 -- 3
2 вершинасы точка сочленения болады

Қай жерде қолданылады?

  • графтағы слабое место табу
  • жолдар мен көпірлер жүйесінде
  • компьютерлік network анализінде
  • байланыс графтарында
  • компоненттермен жұмыс істегенде
  • DFS тақырыбындағы олимпиадалық задачаларда

Негізгі идея

Мосттар мен точка сочленения табу үшін DFS қолданылады. Әр вершина үшін екі мән сақтаймыз:

  • tin[v] — v вершинасына бірінші кірген уақыт
  • low[v] — v немесе оның поддеревосынан жетуге болатын ең кіші tin
int tin[N];
int low[N];
int timer;
tin және low арқылы біз поддерево жоғарыға қайтып шыға ала ма, жоқ па — соны түсінеміз.

tin деген не?

tin[v] — DFS бірінші рет v вершинасына кірген уақыт.

Мысалы:

dfs(1) → tin[1] = 0
dfs(2) → tin[2] = 1
dfs(3) → tin[3] = 2 
tin[v] = timer;
low[v] = timer;
timer++;

low деген не?

low[v] — v вершинасынан немесе оның DFS поддеревосынан жетуге болатын ең ерте кірген вершина уақыты.

low мына жерлер арқылы жаңаруы мүмкін:

  • v-ның өзінің tin мәні арқылы
  • v-ның child вершинасының low мәні арқылы
  • обратное ребро арқылы
Егер child поддеревосы v-дан жоғарыға шыға алмаса, онда v мен child арасындағы ребро мост болуы мүмкін.

tin және low үшін DFS

void dfs(int v, int p) {
    used[v] = true;
    tin[v] = low[v] = timer++;

    for (int to : g[v]) {
        if (to == p) {
            continue;
        }

        if (used[to]) {
            low[v] = min(low[v], tin[to]);
        } else {
            dfs(to, v);
            low[v] = min(low[v], low[to]);
        }
    }
}

Мұнда:

  • v — қазіргі вершина
  • p — DFS бойынша parent
  • to — көрші вершина

Мост шарты

DFS-та v вершинасынан to child вершинасына өттік делік. Сонда v--to ребросы мост болады, егер: 

low[to] > tin[v]

Мағынасы:

low[to] > tin[v]
to поддеревосынан v-ға немесе v-дан жоғарыға жол жоқ
демек v--to жалғыз байланыс
сондықтан бұл ребро — мост

Задача 1: барлық мостты табу

Неориентированный граф берілген. Барлық мосттарды шығару керек.

Input

5 5
1 2
2 3
3 1
3 4
4 5

Output

3 4
4 5

Мұнда 3--4 және 4--5 ребролары мост.

Мосттарды табу толық коды

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, m;
vector<int> g[N];
bool used[N];
int tin[N];
int low[N];
int timer = 0;

void dfs(int v, int p) {
    used[v] = true;
    tin[v] = low[v] = timer++;

    for (int to : g[v]) {
        if (to == p) {
            continue;
        }

        if (used[to]) {
            low[v] = min(low[v], tin[to]);
        } else {
            dfs(to, v);
            low[v] = min(low[v], low[to]);

            if (low[to] > tin[v]) {
                cout << v << ' ' << to << '\n';
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
        g[b].push_back(a);
    }

    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            dfs(i, -1);
        }
    }

    return 0;
}

Маңызды момент: бірнеше бірдей ребро

Егер екі вершина арасында бірнеше ребро болса, жай ғана to == p тексеруі қате жауап беруі мүмкін.

Дұрыс жол — әр реброға id беру. 

vector<pair<int, int>> g[N];

Мұнда:

  • first — көрші вершина
  • second — реброның номері

Мосттарды id арқылы табу

void dfs(int v, int parentEdge) {
    used[v] = true;
    tin[v] = low[v] = timer++;

    for (auto edge : g[v]) {
        int to = edge.first;
        int id = edge.second;

        if (id == parentEdge) {
            continue;
        }

        if (used[to]) {
            low[v] = min(low[v], tin[to]);
        } else {
            dfs(to, id);
            low[v] = min(low[v], low[to]);

            if (low[to] > tin[v]) {
                bridges.push_back(id);
            }
        }
    }
}

Мосттар id-пен толық реализация

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, m;
vector<pair<int, int>> g[N];
bool used[N];
int tin[N];
int low[N];
int timer = 0;
vector<int> bridges;

void dfs(int v, int parentEdge) {
    used[v] = true;
    tin[v] = low[v] = timer++;

    for (auto edge : g[v]) {
        int to = edge.first;
        int id = edge.second;

        if (id == parentEdge) {
            continue;
        }

        if (used[to]) {
            low[v] = min(low[v], tin[to]);
        } else {
            dfs(to, id);
            low[v] = min(low[v], low[to]);

            if (low[to] > tin[v]) {
                bridges.push_back(id);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    vector<pair<int, int>> edges(m + 1);

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;

        edges[i] = {a, b};

        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }

    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            dfs(i, -1);
        }
    }

    sort(bridges.begin(), bridges.end());

    for (int id : bridges) {
        cout << edges[id].first << ' ' << edges[id].second << '\n';
    }

    return 0;
}

Точка сочленения шарты

DFS-та v вершинасынан to child вершинасына өттік делік. v точка сочленения болуы мүмкін, егер: 

low[to] >= tin[v]

Мағынасы:

low[to] >= tin[v]
to поддеревосы v-дан жоғарыға шыға алмайды
v өшсе, to поддеревосы бөлініп кетеді
Мостта шарт >, ал точка сочлененияда шарт >=.

DFS root үшін ерекше жағдай

DFS root үшін бөлек шарт бар.

Root точка сочленения болады, егер оның DFS tree ішінде child саны 1-ден көп болса. 

if (p == -1 && children > 1) {
    isCut[v] = true;
}
Егер root-тың тек бір child-ы болса, root өшсе де компонент саны көбеймейді.

Задача 2: articulation points табу

Неориентированный граф берілген. Барлық точка сочленения шығару керек.

Input

5 5
1 2
2 3
3 1
3 4
4 5

Output

3 4

Мұнда 3 және 4 articulation point болады.

Точка сочленения толық реализация

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, m;
vector<int> g[N];
bool used[N];
bool isCut[N];
int tin[N];
int low[N];
int timer = 0;

void dfs(int v, int p) {
    used[v] = true;
    tin[v] = low[v] = timer++;

    int children = 0;

    for (int to : g[v]) {
        if (to == p) {
            continue;
        }

        if (used[to]) {
            low[v] = min(low[v], tin[to]);
        } else {
            dfs(to, v);
            low[v] = min(low[v], low[to]);

            if (low[to] >= tin[v] && p != -1) {
                isCut[v] = true;
            }

            children++;
        }
    }

    if (p == -1 && children > 1) {
        isCut[v] = true;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
        g[b].push_back(a);
    }

    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            dfs(i, -1);
        }
    }

    for (int i = 1; i <= n; i++) {
        if (isCut[i]) {
            cout << i << ' ';
        }
    }

    return 0;
}

Мост пен articulation point бірге

Бір DFS ішінде екеуін де табуға болады.

Негізгі шарттар:

мост: low[to] > tin[v]
articulation point: low[to] >= tin[v]

Айырмашылық:

  • > — мост үшін
  • >= — articulation point үшін

Мост және articulation point бірге толық код

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, m;
vector<int> g[N];
bool used[N];
bool isCut[N];
int tin[N];
int low[N];
int timer = 0;
vector<pair<int, int>> bridges;

void dfs(int v, int p) {
    used[v] = true;
    tin[v] = low[v] = timer++;

    int children = 0;

    for (int to : g[v]) {
        if (to == p) {
            continue;
        }

        if (used[to]) {
            low[v] = min(low[v], tin[to]);
        } else {
            dfs(to, v);
            low[v] = min(low[v], low[to]);

            if (low[to] > tin[v]) {
                bridges.push_back({v, to});
            }

            if (low[to] >= tin[v] && p != -1) {
                isCut[v] = true;
            }

            children++;
        }
    }

    if (p == -1 && children > 1) {
        isCut[v] = true;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
        g[b].push_back(a);
    }

    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            dfs(i, -1);
        }
    }

    cout << "Bridges:\n";

    for (auto e : bridges) {
        cout << e.first << ' ' << e.second << '\n';
    }

    cout << "Cut points:\n";

    for (int i = 1; i <= n; i++) {
        if (isCut[i]) {
            cout << i << ' ';
        }
    }

    return 0;
}

Шарттарды қалай есте сақтау?

Не іздейміз? Шарт Мағынасы
Мост low[to] > tin[v] to поддеревосынан v-ға немесе жоғарыға жол жоқ
Точка сочленения low[to] >= tin[v] v өшсе, to поддеревосы бөлінеді
DFS root children > 1 root өшсе, бірнеше бөлік пайда болады

Типтік қателер

  • DFS-ты барлық компоненттен бастамау
  • > және >= шарттарын шатастыру
  • DFS root үшін бөлек жағдайды ұмыту
  • Кратные ребра бар кезде жай to == p қолдану
  • Child DFS-тен кейін low[v] жаңартуды ұмыту
  • Обратное ребро арқылы low[v] жаңартуды ұмыту

Асимптотика

Не істейміз? Уақыт Память
Мост табу O(n + m) O(n + m)
Articulation point табу O(n + m) O(n + m)
Екеуін бірге табу O(n + m) O(n + m)
DFS әр вершина мен әр реброны бірнеше рет қана қарайды. Сондықтан уақыт күрделілігі O(n + m).

Қысқа шаблон

void dfs(int v, int p) {
    used[v] = true;
    tin[v] = low[v] = timer++;

    int children = 0;

    for (int to : g[v]) {
        if (to == p) {
            continue;
        }

        if (used[to]) {
            low[v] = min(low[v], tin[to]);
        } else {
            dfs(to, v);
            low[v] = min(low[v], low[to]);

            if (low[to] > tin[v]) {
                cout << "bridge " << v << ' ' << to << '\n';
            }

            if (low[to] >= tin[v] && p != -1) {
                isCut[v] = true;
            }

            children++;
        }
    }

    if (p == -1 && children > 1) {
        isCut[v] = true;
    }
}