Cod sursa(job #2709361)

Utilizator AlexTacuTacu Alexandru AlexTacu Data 20 februarie 2021 10:54:05
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,m,nr;
int viz[100005];

vector <int> v[100005];
vector <int> vt[100005];
vector <int> rez[100005];

stack <int> s;

void cit()
{
    in>>n>>m;
    while(m--)
    {
        int a,b;
        in>>a>>b;
        v[a].push_back(b);
        vt[b].push_back(a);
    }
}

void dfs(int nod)
{
    viz[nod]=1;
    for(size_t i=0; i<v[nod].size(); i++)
    {
        int vecin=v[nod][i];
        if(!viz[vecin])
            dfs(vecin);
    }
    s.push(nod);
}

void dfst(int nod)
{
    viz[nod]=1;
    rez[nr].push_back(nod);
    for(size_t i=0; i<vt[nod].size(); i++)
    {
        int vecin=vt[nod][i];
        if(!viz[vecin])
            dfst(vecin);
    }
}

void prg()
{
    for(int i=1; i<=n; i++)
    {
        if(!viz[i])
            dfs(i);
    }
    fill(viz+1,viz+n+1,0);
    while(!s.empty())
    {
        int nod=s.top();
        s.pop();
        if(!viz[nod])
        {
            nr++;
            dfst(nod);
        }
    }
}

void afis()
{
    out<<nr<<'\n';
    for(int i=1; i<=nr; i++)
    {
        for(size_t j=0; j<rez[i].size(); j++)
            out<<rez[i][j]<<' ';
        out<<'\n';
    }
}

int main()
{
    cit();
    prg();
    afis();
    return 0;
}