Cod sursa(job #2867990)

Utilizator cdenisCovei Denis cdenis Data 10 martie 2022 17:57:07
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int MAX=1e5+5;
int n,m,a,b,viz1[MAX],viz2[MAX],ctc;
vector < int > v[MAX],g[MAX],c[MAX],st;

void DFS1(int nod)
{
    viz1[nod]=1;
    for(auto vec : v[nod])
        if(!viz1[vec])
            DFS1(vec);
    st.push_back(nod);
}

void DFS2(int nod)
{
    c[ctc].push_back(nod);
    viz2[nod]=1;
    for(auto vec : g[nod])
        if(!viz2[vec])
            DFS2(vec);
}

int main()
{
    fin >> n >> m;
    while(m--)
    {
        fin >> a >> b;
        v[a].push_back(b);
        g[b].push_back(a);
    }
    DFS1(1);
    while(!st.empty())
    {
        int nod=st.back();
        st.pop_back();
        if(!viz2[nod])
        {
            ctc++;
            DFS2(nod);
        }
    }
    fout << ctc << '\n';
    for(int i=1;i<=n;i++, fout << '\n')
        for(auto x : c[i])
            fout << x << " ";
    return 0;
}