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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Строка 36: Строка 36:
Построение конденсации:
Построение конденсации:


  unordered_map<int, vector<int>> graph, graphR, graphC;  
  struct Graph {
unordered_set<int> visited;
    int vertexCount, sccCount;
vector<int> order;
    map<int, set<int>> g, gr, gc;
    set<int> visited;
    vector<int> order;
    map<int, int> sccIndexOf, sccSize;
   
   
void dfs1(int v) {
    Graph(int vertexCount) : vertexCount(vertexCount), sccCount(0) {}
    visited.insert(v);
    for (int to : graph[v])
        if (!visited.count(to))
            dfs1(to);
    order.push_back(v);
}
   
   
unordered_map<int, int> scc;
    void addEdge(int a, int b) {
        g[a].insert(b);
        gr[b].insert(a);
    }
   
   
void dfs2(int v, int component) {
    void dfs1(int v) {
    visited.insert(v);
        visited.insert(v);
    scc[v] = component;
        for (int to : g[v])
    for (int to : graphR[v]) {
            if (!visited.count(to))
        if (!visited.count(to))
                dfs1(to);
            dfs2(to, component);
        order.push_back(v);
     }
     }
}
   
   
int main() {
    void dfs2(int v, int component) {
    int vertexCount, edgeCount;
        visited.insert(v);
     cin >> vertexCount >> edgeCount;
        sccIndexOf[v] = component;
        sccSize[component]++;
        for (int to : gr[v]) {
            if (!visited.count(to))
                dfs2(to, component);
        }
     }
   
   
     for (int i = 0; i < edgeCount; i++) {
     void condense() {
         int a, b;
         for (int v = 0; v < vertexCount; v++)
        cin >> a >> b;
            if (!visited.count(v))
        graph[a].push_back(b);
                dfs1(v);
        graphR[b].push_back(a);
        reverse(order.begin(), order.end());
    }
   
    for (int v = 0; v < vertexCount; v++)
        if (!visited.count(v))
            dfs1(v);
    reverse(order.begin(), order.end());
   
   
    visited.clear();
        visited.clear();
    int sccN = 0;
        for (int v : order)
    for (int v : order)
            if (!visited.count(v))
        if (!visited.count(v))
                dfs2(v, sccCount++);
            dfs2(v, sccN++);
   
   
    for (int v = 0; v < vertexCount; v++)
        for (int v = 0; v < vertexCount; v++)
        for (int to : graph[v])
            for (int to : g[v])
            if (scc[v] != scc[to])
                if (sccIndexOf[v] != sccIndexOf[to])
                graphC[scc[v]].push_back(scc[to]);
                    gc[sccIndexOf[v]].insert(sccIndexOf[to]);
  }
    }
  };


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

Версия от 07:16, 8 июля 2021

  • Упорядочиваем вершины по убыванию времени выхода (как при топологической сортировке).
  • Транспонируем граф.
  • Обходим вершины транспонированного графа в порядке убывания времени выхода ("порядке топологической сортировки").
vector<vector<int>> graph(vertexCount), graphR(vertexCount);
vector<int> visited(vertexCount);
vector<int> order;

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) {
    visited[v] = component;
    for (int to : graphR[v])
        if (!visited[to])
            dfs2(to, component);
}

for (int v = 0; v < vertexCount; v++)
    if (!visited[v])
        dfs1(v);
reverse(order.begin(), order.end());

fill(visited.begin(), visited.end(), 0);

int componentCount = 0;
for (int v : order)
    if (!visited[v])
        dfs2(v, ++componentCount);

Построение конденсации:

struct Graph {
    int vertexCount, sccCount;
    map<int, set<int>> g, gr, gc;
    set<int> visited;
    vector<int> order;
    map<int, int> sccIndexOf, sccSize;

    Graph(int vertexCount) : vertexCount(vertexCount), sccCount(0) {}

    void addEdge(int a, int b) {
        g[a].insert(b);
        gr[b].insert(a);
    }

    void dfs1(int v) {
        visited.insert(v);
        for (int to : g[v])
            if (!visited.count(to))
                dfs1(to);
        order.push_back(v);
    }

    void dfs2(int v, int component) {
        visited.insert(v);
        sccIndexOf[v] = component;
        sccSize[component]++;
        for (int to : gr[v]) {
            if (!visited.count(to))
                dfs2(to, component);
        }
    }

    void condense() {
        for (int v = 0; v < vertexCount; v++)
            if (!visited.count(v))
                dfs1(v);
        reverse(order.begin(), order.end());

        visited.clear();
        for (int v : order)
            if (!visited.count(v))
                dfs2(v, sccCount++);

        for (int v = 0; v < vertexCount; v++)
            for (int to : g[v])
                if (sccIndexOf[v] != sccIndexOf[to])
                    gc[sccIndexOf[v]].insert(sccIndexOf[to]);
    }
};

Ссылки

Теория:

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

Код:

Задачи: