Cod sursa(job #2223592)

Utilizator berindeiChesa Matei berindei Data 20 iulie 2018 18:40:09
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>
using namespace std;
int const NMAX=1e5+100;
ifstream in("ctc.in");
ofstream out("ctc.out");

vector<int> g[NMAX], gt[NMAX];
deque<int> top;
bitset<NMAX> viz;
vector< vector<int> > ans;

void dfs_top(int n){
    viz[n]=true;
    for (auto fiu: g[n])
        if (!viz[fiu]) dfs_top(fiu);
    top.push_front(n);
}

void dfs_ctc(int n, vector<int>& v){
    viz[n]=true;
    v.push_back(n);
    for (auto fiu: gt[n])
        if (!viz[fiu]) dfs_ctc(fiu, v);
}

int main(){
    int n, m, n1, n2;
    in >> n >> m;
    for (int i=1; i<=m; i++){
        in >> n1 >> n2;
        g[n1].push_back(n2);
        gt[n2].push_back(n1);
    }
    for (int i=1; i<=n; i++)
        if (!viz[i]) dfs_top(i);
    
    viz.reset();
    for (auto x: top){
        if (viz[x]) continue;
        vector<int> sol;
        dfs_ctc(x, sol);
        ans.push_back(sol);
    }
    out << ans.size() << '\n';
    for (auto& x: ans){
        for (auto y: x)
            out << y << ' ';
        out << '\n';
    }
}