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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
  • Упорядочиваем вершины по убыванию времени выхода (как при топологической сортировке).
  • Транспонируем граф.
  • Обходим вершины транспонированного графа в порядке убывания времени выхода ("порядке топологической сортировки").
vector<int> g[V_CNT], gR[V_CNT];
int u[V_CNT];
vector<int> order;

void dfs1(int v) {
    u[v] = 1;
    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) {
    u[v] = k;
    for (int i = 0; i < gR[v].size(); i++)
        if (!u[gR[v][i]])
            dfs2(gR[v][i], k);
}

for (int i = 0; i < V_CNT; i++)
    u[i] = 0;
for (int i = 0; i < V_CNT; i++)
    if (!u[i])
        dfs1(i);
reverse(order.begin(), order.end());
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;
vector<int> order;
void dfs1(int v) {
    visited.insert(v);
    for (int to : g[v]) {
        if (!visited.count(to))
            dfs1(to);
    }
    order.push_back(v);
}

unordered_map<int, int> scc;
void dfs2(int v, int sccN) {
    visited.insert(v);
    scc[v] = sccN;
    for (int to : gr[v]) {
        if (!visited.count(to))
            dfs2(to, sccN);
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        string a, b;
        cin >> a >> b;
        g[a].push_back(b);
        gr[b].push_back(a);
    }
   
    for (int v = 0; v < n; v++) {
        if (!visited.count(v))
            dfs1(v);
    }
    reverse(order.begin(), order.end());

    visited.clear();
    int sccN = 0;
    for (int i = 0; i < order.size(); i++) {
        if (!visited.count(order[i]))
            dfs2(order[i], sccN++);
    }

    for (int v = 0; v < n; v++) {
        for (int to : g[v])
            if (scc[v] != scc[to])
                gc[scc[v]].push_back(scc[to]);
    }
}

Ссылки

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