Cod sursa(job #2866828)

Utilizator adiaioanaAdia R. adiaioana Data 9 martie 2022 23:49:01
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <list>
#include <algorithm>
#include <vector>
#define pb push_back
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");

int N, viz[100100], viz2[100100];
list <int> parg;
vector <int> sol, G[100100], G_inv[100100];
vector <vector <int> > ctc;

void mark(int nod);
void dfs(int nod);
int main()
{
    int M,x,y;
    cin>>N>>M;
    for(int i=1; i<=M; ++i)
    {
        cin>>x>>y;
        G[x].pb(y);
        G_inv[y].pb(x);
    }

    for(int i=1; i<=N; ++i)
        if(!viz[i])
        {
            viz[i]=1;
            dfs(i);
        }

    int nod;
    while(!parg.empty())
    {
        nod=parg.back(); parg.pop_back();
        if(!viz2[nod])
        {
            mark(nod);
            ctc.pb(sol);
            sol.clear();
        }
    }

    cout<<ctc.size()<<'\n';
    for(auto V:ctc){
        sort(V.begin(),V.end());
        for(auto it:V)
            cout<<it<<' ';
        cout<<'\n';
    }
    return 0;
}

void mark(int nod)
{
    viz2[nod]=ctc.size()+1;
    sol.pb(nod);
    for(auto nn:G_inv[nod])
        if(!viz2[nn])
            mark(nn);
}

void dfs(int nod)
{
    for(auto nn: G[nod])
        if(!viz[nn]){
            viz[nn]=1;
            dfs(nn);
        }
    parg.pb(nod);
}