Cod sursa(job #3337179)

Utilizator DavidAA007Apostol David DavidAA007 Data 26 ianuarie 2026 23:34:28
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int>f;
int n,m,i,j,contor,x,y,viz[100005],ctc[100005],v[100005];
vector<int>G[100005],Gt[100005];
vector<int>ans[100005];
void dfs1(int nod)
{
    viz[nod]=1;
    for(auto x:G[nod])
        if(!viz[x])
            dfs1(x);
    f.push_back(nod);
}
void dfs2(int nod)
{
    v[nod]=1;
    ans[contor].push_back(nod);
    for(auto x:Gt[nod])
        if(!v[x])
        {
            dfs2(x);
        }
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        G[x].push_back(y);
        Gt[y].push_back(x);
    }
    for(i=1;i<=n;i++)
        if(!viz[i])
            dfs1(i);
    contor=0;

    while(!f.empty())
    {
        int k=f.back();
        f.pop_back();
        if(!v[k])
        {
            dfs2(k);
            contor++;
        }
    }
    fout<<contor<<"\n";
    for(i=0;i<contor;i++)
    {
        for(auto y:ans[i])
        {
            fout<<y<<" ";
        }
        fout<<"\n";
    }
    return 0;
}