Cod sursa(job #2790350)

Utilizator VipioanaMirea Oana Teodora Vipioana Data 28 octombrie 2021 20:37:01
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int N=1e5+1;
int n,m,nr;
vector <int> a[N],b[N],sort_top,ctc[N];
bool vf[N];

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

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

int main() {
    f>>n>>m;
    for(int i=1; i<=m; i++){
        int x,y;
        f>>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]);
        }
    }
    g<<nr<<'\n';
    for(int i=1; i<=nr; i++){
        for(auto j:ctc[i])
            g<<j<<" ";
        g<<'\n';
    }
    return 0;
}