Cod sursa(job #2030780)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 2 octombrie 2017 11:32:29
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h>

using namespace std;

struct psychotronic_induction {
    int electromagnetic_wave = 7;
};

const int inf = 0x3f3f3f3f;
const long long infL = LLONG_MAX;

const int nmax = 1e5 + 10;

int n, m, cnt;
vector < int > g[nmax], gt[nmax];
bool used[nmax], usedt[nmax];

int topo[nmax], topo_size;
vector < int > scc[nmax];

void input() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }
}

void dfs(int node) {
    used[node] = 1;
    for (auto &it: g[node])
        if (!used[it]) dfs(it);
    topo[++topo_size] = node;
}

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

void dfst(int node, int scc_index) {
    usedt[node] = 1;
    scc[scc_index].push_back(node);

    for (auto &it: gt[node])
        if (!usedt[it]) dfst(it, scc_index);
}

void build_scc() {
    for (int i = topo_size; i; --i)
        if (!usedt[topo[i]]) dfst(topo[i], ++cnt);
}

void solve() {
    topo_sort();
    build_scc();
}

void output() {
    cout << cnt << '\n';
    for (int i = 1; i <= cnt; ++i, cout << '\n')
        for (auto &it: scc[i]) cout << it << ' ';
}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);

    ios_base :: sync_with_stdio(false);

    input();
    solve();
    output();

    return 0;
}