Компоненты сильной связности. Алгоритм Косараю-Шарира: различия между версиями

Текущая версия от 15:33, 30 июня 2023

TLDR

Код

Упорядочиваем вершины по убыванию времени выхода (как при топологической сортировке).
Транспонируем граф.
Обходим вершины транспонированного графа в порядке убывания времени выхода ("порядке топологической сортировки").

struct Graph {
    vector<vector<int>> graph, graphR;
    vector<int> visited, order, sccOf;

    Graph(int vertexCount) :
        graph(vertexCount), graphR(vertexCount) {}

    void addEdge(int a, int b) {
        graph[a].push_back(b);
        graphR[b].push_back(a);
    }

    void dfs1(int v) {
        visited[v] = 1;
        for (int to : graph[v])
            if (!visited[to])
                dfs1(to);
        order.push_back(v);
    }

    void dfs2(int v, int component) {
        sccOf[v] = component;
        for (int to : graphR[v])
            if (sccOf[to] == -1)
                dfs2(to, component);
    }

    vector<int> getScc() {
        visited.assign(graph.size(), 0);
        for (int v = 0; v < graph.size(); v++)
            if (!visited[v])
                dfs1(v);
        reverse(order.begin(), order.end());

        sccOf.assign(graph.size(), -1);
        int sccCount = 0;
        for (int v : order)
            if (sccOf[v] == -1)
                dfs2(v, sccCount++);

        return sccOf;
    }
};

struct Graph {
    vector<vector<int>> graph, graphR;
    vector<int> visited, order, sccOf;

    Graph(int vertexCount) :
        graph(vertexCount), graphR(vertexCount) {}

    void addEdge(int a, int b) {
        graph[a].push_back(b);
        graphR[b].push_back(a);
    }

    void dfs1(int v) {
        visited[v] = 1;
        for (int to : graph[v])
            if (!visited[to])
                dfs1(to);
        order.push_back(v);
    }

    void dfs2(int v, int component) {
        sccOf[v] = component;
        for (int to : graphR[v])
            if (sccOf[to] == -1)
                dfs2(to, component);
    }

    vector<set<int>> condense() {
        visited.assign(graph.size(), 0);
        for (int v = 0; v < graph.size(); v++)
            if (!visited[v])
                dfs1(v);
        reverse(order.begin(), order.end());

        sccOf.assign(graph.size(), -1);
        int sccCount = 0;
        for (int v : order)
            if (sccOf[v] == -1)
                dfs2(v, sccCount++);

        vector<set<int>> graphC(sccCount);
        for (int v = 0; v < graph.size(); v++)
            for (int to : graph[v])
                if (sccOf[v] != sccOf[to])
                    graphC[sccOf[v]].insert(sccOf[to]);

        return graphC;
    }
};

Ссылки

Теория:

Демонстрация:

VisuAlgo — Graph Traversal

Код:

Задачи:

informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 2

@@ Строка 1: / Строка 1: @@
+== TLDR ==
+<youtube width="300" height="180">-UgiBh1IMQU</youtube>
+== Код ==
 * Упорядочиваем вершины по убыванию времени выхода (как при топологической сортировке).
 * Транспонируем граф.
 * Обходим вершины транспонированного графа в порядке убывания времени выхода ("порядке топологической сортировки").
-  vector<int> g[V_CNT], gR[V_CNT];
+{|width=100%
- int u[V_CNT];
+|width=50%|
- vector<int> order;
+  struct Graph {
+     vector<vector<int>> graph, graphR;
+     vector<int> visited, order, sccOf;
- void dfs1(int v) {
+      Graph(int vertexCount) :
-     u[v] = 1;
+          graph(vertexCount), graphR(vertexCount) {}
-      for (int i = 0; i < g[v].size(); i++)
-          if (!u[g[v][i]])
-             dfs1(g[v][i]);
-     order.push_back(v);
- }
- void dfs2(int v, int k) {
+     void addEdge(int a, int b) {
-     u[v] = k;
+         graph[a].push_back(b);
-     for (int i = 0; i < gR[v].size(); i++)
+          graphR[b].push_back(a);
-          if (!u[gR[v][i]])
+     }
-             dfs2(gR[v][i], k);
- }
- for (int i = 0; i < V_CNT; i++)
+     void dfs1(int v) {
-     u[i] = 0;
+         visited[v] = 1;
- for (int i = 0; i < V_CNT; i++)
+         for (int to : graph[v])
-     if (!u[i])
+             if (!visited[to])
-         dfs1(i);
+                 dfs1(to);
- reverse(order.begin(), order.end());
+         order.push_back(v);
- for (int i = 0; i < V_CNT; i++)
+      }
-      u[i] = 0;
- int k = 1;
- for (int i = 0; i < V_CNT; i++)
-     if (!u[order[i]])
-         dfs2(order[i], k++);
-Построение конденсации:
- unordered_map<int, vector<int>> g, gr, gc;
- unordered_set<int> visited;
+     void dfs2(int v, int component) {
- vector<int> order;
+         sccOf[v] = component;
- void dfs1(int v) {
+         for (int to : graphR[v])
-     visited.insert(v);
+             if (sccOf[to] == -1)
-     for (int to : g[v]) {
+                 dfs2(to, component);
-         if (!visited.count(to))
-             dfs1(to);
       }
-     order.push_back(v);
- }
- unordered_map<int, int> scc;
+     vector<int> getScc() {
- void dfs2(int v, int sccN) {
+         visited.assign(graph.size(), 0);
-     visited.insert(v);
+         for (int v = 0; v < graph.size(); v++)
-     scc[v] = sccN;
+             if (!visited[v])
-     for (int to : gr[v]) {
+                 dfs1(v);
-          if (!visited.count(to))
+         reverse(order.begin(), order.end());
-              dfs2(to, sccN);
+          sccOf.assign(graph.size(), -1);
+         int sccCount = 0;
+         for (int v : order)
+              if (sccOf[v] == -1)
+                 dfs2(v, sccCount++);
+         return sccOf;
       }
-  }
+  };
+|width=50%|
+ struct Graph {
+     vector<vector<int>> graph, graphR;
+     vector<int> visited, order, sccOf;
- int main() {
+     Graph(int vertexCount) :
-     int n, m;
+         graph(vertexCount), graphR(vertexCount) {}
-     cin >> n >> m;
-      for (int i = 0; i < m; i++) {
+      void addEdge(int a, int b) {
-         string a, b;
+          graph[a].push_back(b);
-         cin >> a >> b;
+          graphR[b].push_back(a);
-          g[a].push_back(b);
-          gr[b].push_back(a);
       }
-      for (int v = 0; v < n; v++) {
+      void dfs1(int v) {
-         if (!visited.count(v))
+         visited[v] = 1;
-             dfs1(v);
+         for (int to : graph[v])
+             if (!visited[to])
+                 dfs1(to);
+         order.push_back(v);
       }
-     reverse(order.begin(), order.end());
-      visited.clear();
+      void dfs2(int v, int component) {
-     int sccN = 0;
+         sccOf[v] = component;
-     for (int i = 0; i < order.size(); i++) {
+         for (int to : graphR[v])
-         if (!visited.count(order[i]))
+             if (sccOf[to] == -1)
-             dfs2(order[i], sccN++);
+                 dfs2(to, component);
       }
-      for (int v = 0; v < n; v++) {
+      vector<set<int>> condense() {
-          for (int to : g[v])
+         visited.assign(graph.size(), 0);
-             if (scc[v] != scc[to])
+         for (int v = 0; v < graph.size(); v++)
-                 gc[scc[v]].push_back(scc[to]);
+             if (!visited[v])
+                 dfs1(v);
+         reverse(order.begin(), order.end());
+         sccOf.assign(graph.size(), -1);
+         int sccCount = 0;
+         for (int v : order)
+             if (sccOf[v] == -1)
+                 dfs2(v, sccCount++);
+         vector<set<int>> graphC(sccCount);
+          for (int v = 0; v < graph.size(); v++)
+             for (int to : graph[v])
+                 if (sccOf[v] != sccOf[to])
+                     graphC[sccOf[v]].insert(sccOf[to]);
+         return graphC;
       }
-  }
+  };
+|}
 == Ссылки ==
-* [http://e-maxx.ru/algo/strong_connected_components e-maxx.ru &mdash; Поиск компонент сильной связности, построение конденсации графа]
+Теория:
-* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%B0_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83_%D0%B4%D0%BB%D1%8F_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82_%D1%81%D0%B8%D0%BB%D1%8C%D0%BD%D0%BE%D0%B9_%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8 neerc.ifmo.ru/wiki &mdash; Использование обхода в глубину для поиска компонент сильной связности]
+:* [http://e-maxx.ru/algo/strong_connected_components e-maxx.ru &mdash; Поиск компонент сильной связности, построение конденсации графа]
-* [http://algorithmica.org/tg/dfs-plus algorithmica.org — Продвинутый DFS]
+:* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%B0_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83_%D0%B4%D0%BB%D1%8F_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82_%D1%81%D0%B8%D0%BB%D1%8C%D0%BD%D0%BE%D0%B9_%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8 neerc.ifmo.ru/wiki &mdash; Использование обхода в глубину для поиска компонент сильной связности]
-* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru &mdash; Курс &laquo;Алгоритмы на графах&raquo; &mdash; часть 2]
+:* [http://algorithmica.org/tg/dfs-plus algorithmica.org — Продвинутый DFS]
-* [http://github.com/petr-kalinin/progtexts/releases/download/v2014.11.01/04_dfs.pdf Калинин П. Поиск в глубину]
+:* [https://notes.algoprog.ru/dfs/04_3_topsort.html#id5 Калинин П. Компоненты сильной связности]
-* [http://ejudge.btty.su/bmstu/addon/docs/articles/moscow2006-dfs.pdf Лахно А. Поиск в глубину и его применение]
+:* [https://ejudge.lksh.ru/archive/2014/07/Cprime/stuff/Dfs.pdf Лахно А. Поиск в глубину и его применение]
-* [http://algs4.cs.princeton.edu/lectures/42DirectedGraphs.pdf algs4.cs.princeton.edu/lectures &mdash; 4.2 Directed Graphs]
+:* [https://algs4.cs.princeton.edu/lectures/keynote/42DirectedGraphs.pdf algs4.cs.princeton.edu/lectures &mdash; 4.2 Directed Graphs]
-* [http://visualgo.net/dfsbfs.html VisuAlgo &mdash; Graph Traversal]
+Демонстрация:
-* [http://github.com/indy256/codelibrary/blob/master/java/src/SCCKosaraju.java CodeLibrary &mdash; Strongly connected components. Kosaraju's algorithm]
+:* [https://visualgo.net/en/dfsbfs VisuAlgo &mdash; Graph Traversal]
+Код:
+:* [https://github.com/indy256/codelibrary/blob/master/cpp/graphs/dfs/strongly_connected_components.cpp codelibrary/cpp/graphs/dfs/strongly_connected_components.cpp]
+:* [https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/KosarajuSharirSCC.java algs4/KosarajuSharirSCC.java]
+Задачи:
+:* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru &mdash; Курс &laquo;Алгоритмы на графах&raquo; &mdash; часть 2]
 [[Category:Поиск в глубину и его приложения]]

Компоненты сильной связности. Алгоритм Косараю-Шарира: различия между версиями

Текущая версия от 15:33, 30 июня 2023

TLDR

Код

Ссылки

Навигация

Поиск