Cod sursa(job #3004784)

Utilizator CalinHanguCalinHangu CalinHangu Data 16 martie 2023 16:39:37
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

#define pb push_back
#define ll long long

using namespace std;

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

const int NMAX = 1e5 + 5;
const char nl = '\n';

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

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[a].pb(b);
    }
    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;
}