Cod sursa(job #1816121)

Utilizator razvan242Zoltan Razvan-Daniel razvan242 Data 26 noiembrie 2016 09:56:00
Problema Componente tare conexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
// kosaraju

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e5 + 1;

vector<int> v[NMAX], vt[NMAX];
vector<int> ans[NMAX];
int n, m, cnt;
int stk[NMAX], top;
bool viz[NMAX];

void dfs(int node) {
    viz[node] = 1;
    for (const int& x: v[node]) {
        if (!viz[x])
            dfs(x);
    }
    stk[++top] = node;
}

void dfst(int node) {
    viz[node] = 1;
    for (const int& x: vt[node]) {
        if (!viz[x])
            dfst(x);
    }
    ans[cnt].push_back(node);
}

int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    cin >> n >> m;
    for (int x, y; m; --m) {
        cin >> x >> y;
        v[x].push_back(y);
        vt[y].push_back(x);
    }
    for (int i = 1; i <= n; ++i) {
        if (!viz[i])
            dfs(i);
    }
    memset(viz, 0, sizeof viz);
    while (top) {
        if (!viz[stk[top]]) {
            ++cnt;
            dfst(stk[top]);
        }
        --top;
    }
    cout << cnt << '\n';
    for (int i = 1; i <= cnt; ++i, cout << '\n') {
        for (const int& x: ans[i])
            cout << x << ' ';
    }
    return 0;
}