Cod sursa(job #2809644)

Utilizator bostanlucastefanBostan Luca-Stefan bostanlucastefan Data 27 noiembrie 2021 12:12:23
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <algorithm>
#include <fstream>
#include <vector>
#define pb push_back

using namespace std;
using vi=vector<int>;

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

const int N=1e5+2;

vi g[N],ginv[N],ans[N],top;
bool viz[N];

void go(int nod)
{
    viz[nod]=1;
    for(auto i:g[nod])
        if(!viz[i])
            go(i);
    top.pb(nod);
}

void dfs(int nod,int nr)
{
    viz[nod]=1;
    ans[nr].pb(nod);
    for(auto i:ginv[nod])
        if(!viz[i])
            dfs(i,nr);
}

int n,m,u,v,nr,i;

int main()
{
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>u>>v;
        g[u].pb(v);
        ginv[v].pb(u);
    }

    for(i=1; i<=n; i++)
        if(!viz[i])
            go(i);

    for(i=1; i<=n; i++)
        viz[i]=0;

    nr=0;
    for(i=n-1; i>=0; i--)
        if(!viz[top[i]])
            dfs(top[i],++nr);

    fout<<nr<<'\n';
    for(i=1; i<=nr; i++)
    {
        for(auto v:ans[i])
            fout<<v<<' ';
        fout<<'\n';
    }
    return 0;
}