Cod sursa(job #3336085)

Utilizator stefantironTiron Stefan stefantiron Data 24 ianuarie 2026 10:08:44
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <vector>
#include <stack>

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


int n,m,nrctc;

vector<int>CTC[100001],V[100001],VT[100001];
stack<int>st;

bool viz1[100001],viz2[100001];


void dfs1(int x)
{
    viz1[x]=1;
    for(auto&it:V[x])
        if(!viz1[it])
            dfs1(it);
    st.push(x);
}
void dfs2(int x)
{
    viz2[x]=1;
    CTC[nrctc].push_back(x);
    for(auto&it:VT[x])
        if(!viz2[it])
            dfs2(it);
}

int main()
{
    int x,y;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        V[x].push_back(y);
        VT[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
        if(!viz1[i])
            dfs1(i);
    while(st.size())
    {
        if(!viz2[st.top()])
        {
            nrctc++;
            dfs2(st.top());
        }
        st.pop();
    }
    fout<<nrctc<<'\n';
    for(int i=1;i<=nrctc;i++)
    {
        for(auto&it:CTC[i])
            fout<<it<<' ';
        fout<<'\n';
    }

    return 0;
}