Cod sursa(job #3029960)

Utilizator CalinHanguCalinHangu CalinHangu Data 17 martie 2023 12:18:22
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

#define ll long long
#define pb push_back
#define pii pair<int, int>
#define x first
#define y second

using namespace std;

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

const int NMAX = 100005;
const char nl = '\n';

int n, m, len, f[NMAX];

vector<int> v[NMAX], rev[NMAX], order, comp;

vector<vector<int>> ans;

void dfs(int node){
    f[node] = 1;
    for(auto neigh: v[node]){
        if(!f[neigh])
            dfs(neigh);
    }
    order.pb(node);
}

void kosaraju(int node){
    f[node] = 1;
    comp.pb(node);
    for(auto neigh: rev[node]){
        if(!f[neigh])
            kosaraju(neigh);
    }
}

int main()
{
    in >> n >> m;
    for(int i = 1; i <= m; ++i){
        int a, b;
        in >> a >> b;
        v[a].pb(b);
        rev[b].pb(a);
    }
    for(int i = 1; i <= n; ++i){
        if(!f[i])
            dfs(i);
    }
    reverse(order.begin(), order.end());
    for(int i = 1; i <= n; ++i)
        f[i] = 0;
    for(auto i: order){
        if(!f[i]){
            len++;
            kosaraju(i);
            ans.pb(comp);
            comp.clear();
        }
    }
    out << len << nl;
    for(auto i: ans){
        for(auto j: i)
            out << j << ' ';
        out << nl;
    }
    return 0;
}