Cod sursa(job #2815917)

Utilizator VipioanaMirea Oana Teodora Vipioana Data 10 decembrie 2021 16:55:16
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
const int N=1e5+1;
int n,m,nr;
vector <int> a[N],b[N],sort_top,ctc[N];
bitset <N> vf;

void dfs_s(int x) {
    vf[x]=1;
    for(int j:a[x]){
        if(!vf[j])
            dfs_s(j);
    }
    sort_top.push_back(x);
}

void dfs_p(int x) {
    vf[x]=0;
    for(int j:b[x]){
        if(vf[j])
            dfs_p(j);
    }
    ctc[nr].push_back(x);
}

int main() {
    cin>>n>>m;
    for(int i=0; i<m; i++) {
        int x,y;
        cin>>x>>y;
        a[x].push_back(y);
        b[y].push_back(x);
    }
    for(int i=1; i<=n; i++)
        if(!vf[i])
            dfs_s(i);
    for(int i=n-1; i>=0; i--)
        if(vf[sort_top[i]]) {
            nr++;
            dfs_p(sort_top[i]);
        }
    cout<<nr<<'\n';
    for(int i=1; i<=nr; i++) {
        for(int j:ctc[i])
            cout<<j<<" ";
        cout<<'\n';
    }
    return 0;
}