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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 7: Строка 7:
* Обходим вершины транспонированного графа в порядке убывания времени выхода ("порядке топологической сортировки").
* Обходим вершины транспонированного графа в порядке убывания времени выхода ("порядке топологической сортировки").


  vector<vector<int>> graph(vertexCount), graphR(vertexCount);
{|width=100%
  vector<int> visited(vertexCount);
|width=50%|
vector<int> order;
  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) {
    void dfs1(int v) {
    visited[v] = 1;
        visited[v] = 1;
    for (int to : graph[v])
        for (int to : graph[v])
        if (!visited[to])
            if (!visited[to])
            dfs1(to);
                dfs1(to);
    order.push_back(v);
        order.push_back(v);
}
    }
   
   
void dfs2(int v, int component) {
    void dfs2(int v, int component) {
    visited[v] = component;
        sccOf[v] = component;
    for (int to : graphR[v])
        for (int to : graphR[v])
        if (!visited[to])
            if (sccOf[to] == -1)
            dfs2(to, component);
                dfs2(to, component);
}
    }
   
   
for (int v = 0; v < vertexCount; v++)
    vector<int> getScc() {
    if (!visited[v])
        visited.assign(graph.size(), 0);
        dfs1(v);
        for (int v = 0; v < graph.size(); v++)
reverse(order.begin(), order.end());
            if (!visited[v])
                dfs1(v);
        reverse(order.begin(), order.end());
   
   
fill(visited.begin(), visited.end(), 0);
        sccOf.assign(graph.size(), -1);
        int sccCount = 0;
        for (int v : order)
            if (sccOf[v] == -1)
                dfs2(v, sccCount++);
   
   
int componentCount = 0;
        return sccOf;
for (int v : order)
     }
     if (!visited[v])
};
        dfs2(v, ++componentCount);
|width=50%|
 
Построение конденсации:


  struct Graph {
  struct Graph {
     int vertexCount, sccCount;
     vector<vector<int>> graph, graphR;
    map<int, set<int>> g, gr, gc;
     vector<int> visited, order, sccOf;
     set<int> visited;
    vector<int> order;
    map<int, int> sccIndexOf, sccSize;
   
   
     Graph(int vertexCount) : vertexCount(vertexCount), sccCount(0) {}
     Graph(int vertexCount) :
        graph(vertexCount), graphR(vertexCount) {}
   
   
     void addEdge(int a, int b) {
     void addEdge(int a, int b) {
         g[a].insert(b);
         graph[a].push_back(b);
         gr[b].insert(a);
         graphR[b].push_back(a);
     }
     }
   
   
     void dfs1(int v) {
     void dfs1(int v) {
         visited.insert(v);
         visited[v] = 1;
         for (int to : g[v])
         for (int to : graph[v])
             if (!visited.count(to))
             if (!visited[to])
                 dfs1(to);
                 dfs1(to);
         order.push_back(v);
         order.push_back(v);
Строка 63: Строка 75:
   
   
     void dfs2(int v, int component) {
     void dfs2(int v, int component) {
         visited.insert(v);
         sccOf[v] = component;
        sccIndexOf[v] = component;
         for (int to : graphR[v])
        sccSize[component]++;
             if (sccOf[to] == -1)
         for (int to : gr[v]) {
             if (!visited.count(to))
                 dfs2(to, component);
                 dfs2(to, component);
        }
     }
     }
   
   
     void condense() {
     vector<set<int>> condense() {
         for (int v = 0; v < vertexCount; v++)
        visited.assign(graph.size(), 0);
             if (!visited.count(v))
         for (int v = 0; v < graph.size(); v++)
             if (!visited[v])
                 dfs1(v);
                 dfs1(v);
         reverse(order.begin(), order.end());
         reverse(order.begin(), order.end());
   
   
         visited.clear();
         sccOf.assign(graph.size(), -1);
        int sccCount = 0;
         for (int v : order)
         for (int v : order)
             if (!visited.count(v))
             if (sccOf[v] == -1)
                 dfs2(v, sccCount++);
                 dfs2(v, sccCount++);
   
   
         for (int v = 0; v < vertexCount; v++)
        vector<set<int>> graphC(sccCount);
             for (int to : g[v])
         for (int v = 0; v < graph.size(); v++)
                 if (sccIndexOf[v] != sccIndexOf[to])
             for (int to : graph[v])
                     gc[sccIndexOf[v]].insert(sccIndexOf[to]);
                 if (sccOf[v] != sccOf[to])
                     graphC[sccOf[v]].insert(sccOf[to]);
        return graphC;
     }
     }
  };
  };
|}


== Ссылки ==
== Ссылки ==

Текущая версия от 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;
    }
};

Ссылки

Теория:

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

Код:

Задачи:

Источник — https://acm.khpnets.info/w39/index.php?title=Компоненты_сильной_связности._Алгоритм_Косараю-Шарира&oldid=2900