Cod sursa(job #2928510)

Utilizator catalin28Gheorghe Catalin catalin28 Data 23 octombrie 2022 09:31:45
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
// Kosaraju's algorithm
#include <bits/stdc++.h>
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

const int con = 1e5 + 5;

vector<int> lad[con], rev[con], post, temp, comps[con], comp;
int n, m, a, b, num_comp;

void dfs(int current, int current_comp = -2)
{
    if(comp[current] != -1) return;
    comp[current] = current_comp;

    for (auto nb : lad[current])
    {
        dfs(nb, current_comp);
    }

    post.push_back(current);
}

void kosaraju()
{
    comp.assign(n+1, -1);
    for (int i = 1; i <= n; i++) dfs(i);

    for (int i = 1; i <= n; i++)
            for (auto j : lad[i]) rev[j].push_back(i);

    swap(rev, lad);
    reverse(post.begin(), post.end());

    comp.assign(n+1, -1);
    for (int i = 0; i < n; i++)
        if(comp[post[i]] == -1)
        {dfs(post[i], num_comp++);}

}

int main()
{
    f >> n >> m;
    for(int i = 1; i <= m; i ++)
    {
        f >> a >> b;
        lad[a].push_back(b);
    }
    kosaraju();
    cout << num_comp << "\n";
    for(int i = 1; i <= n; i++)
        comps[comp[i]].push_back(i);
    for(int i = 0; i < num_comp; i++)
        {
            for(auto a:comps[i])
                cout << a << " ";
            cout << "\n";
        }
    return 0;
}