Cod sursa(job #2272012)

Utilizator ContDeRacistAliniateEBlat ContDeRacist Data 29 octombrie 2018 16:42:33
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

ifstream cin("ctc.in");
ofstream cout("ctc.out");

const int N = 1e3 + 7;

vector < int > stop, np[N], adia[N], reva[N];
bool viz[N];
int c[N];

int n, nc(0);

void dfs(int nod) {
    viz[nod] = 1;
    for (auto i : adia[nod])
        if (!viz[i])
            dfs(i);
    stop.push_back(nod);
}

void mk_tps() {
    for (int i = 1; i <= n; ++i)
        if (!viz[i])
            dfs(i);
}

void scd(int nod, int cp) {
    viz[nod] = 1;
    c[nod] = cp;
    np[cp].push_back(nod);
    for (auto i : reva[nod])
        if (!viz[i])
            scd(i, cp);
}

void mk_scc() {
    memset(viz, 0, sizeof viz);
    for (int i = n - 1; i >= 0; --i)
        if (!viz[stop[i]])
            scd(stop[i], ++nc);
}

int main()
{
    int m, a, b;
    cin >> n >> m;
    while (m--) {
        cin >> a >> b;
        adia[a].push_back(b);
        reva[b].push_back(a);
    }
    mk_tps();
    mk_scc();
    cout << nc << '\n';
    for (int i = 1; i <= nc; ++i) {
        for (auto p : np[i])
            cout << p << ' ';
        cout << '\n';
    }
    return 0;
}