Cod sursa(job #2651647)

Utilizator adiaioanaAdia R. adiaioana Data 23 septembrie 2020 10:41:12
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <vector>
#define pb push_back
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int viz[100100],viz2[100100],n;
vector <int> sol, G[100100], G_inv[100100], List;
vector < vector <int> > ctc;
void dfs(int nod)
{
    viz[nod]=1;
    for(auto nn:G[nod])
        if(!viz[nn])
            dfs(nn);
    List.pb(nod);
}

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

int main()
{
    int m,x,y,el,k=0;
    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])
        {
            ++k;
            dfs(i);
        }
    while(!List.empty())
    {
        el=List.back();
        if(!viz2[el])
        {
            mark(el);
            ctc.pb(sol);
            sol.clear();
        }
        List.pop_back();
    }
    cout<<ctc.size()<<'\n';
    for(auto it:ctc)
    {
        for(auto it1:it)
            cout<<it1<<' ';
        cout<<'\n';
    }
    return 0;
}