Cod sursa(job #2430294)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 13 iunie 2019 20:37:14
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5;
#define pb push_back

vector <int> gr[1 + MAX_N], invgr[1 + MAX_N];
vector <int> ord;
vector <int> comp[1 + MAX_N];
bool viz[1 + MAX_N];
int nr;
void dfs1 (int node) {
    viz[node] = 1;
    for (int &vec : gr[node])
        if (!viz[vec])
            dfs1 (vec);
    ord.pb (node);
}

void dfs2 (int node) {
    comp[nr].pb (node);
    viz[node] = 0;
    for (int &vec : invgr[node])
        if (viz[vec])
            dfs2 (vec);
}

int main() {
    freopen ("ctc.in", "r", stdin);
    freopen ("ctc.out", "w", stdout);
    int n, m;
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    cin >> n >> m;
    while (m--) {
        int x, y;
        cin >> x >> y;
        gr[x].pb (y);
        invgr[y].pb (x);
    }
    for (int i = 1; i <= n; i++)
        if (!viz[i])
            dfs1 (i);
    nr = 0;
    reverse (ord.begin (), ord.end ());
    for (int &node : ord)
        if (viz[node]) {
            nr++;
            dfs2 (node);
        }
    cout << nr << "\n";
    for (int i = 1; i <= nr; i++) {
        for (int &node : comp[i])
            cout << node << " ";
        cout << "\n";
    }
    return 0;
}