Cod sursa(job #3344352)

Utilizator robertcosacCosac Robert-Mihai robertcosac Data 1 martie 2026 21:15:02
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> v[100009], vt[100009];
vector <int> ans[100009];
int cnt=0;
vector <int> srt;
int in[100009];
bool viz[100009];
void dfs (int nod)
{
    srt.push_back(nod);
    viz[nod]=1;
    for (auto y:v[nod])
    {
        if (!viz[y])
        {
            in[y]--;
            if (!in[y])
                dfs (y);
        }
    }
}
void dfst (int nod)
{
    ans[cnt].push_back(nod);
    viz[nod]=1;
    for (auto y:vt[nod])
    {
        if (!viz[y])
            dfst (y);
    }
}
signed main ()
{
    int n, m;
    f >> n >> m;
    for (int i=1; i<=m; i++)
    {
        int x, y;
        f >> x >> y;
        v[x].push_back(y);
        vt[y].push_back(x);
    }
    for (int i=1; i<=n; i++)
    {
        if (!viz[i] && !in[i])
            dfs (i);
    }
    for (int i=1; i<=n; i++)
        viz[i]=0;
    for (int i=1; i<=n; i++)
        if (!viz[i])
        cnt++, dfst(i);
    g << cnt << '\n';
    for (int i=1; i<=cnt; i++)
    {
        for (auto x:ans[i]) g << x << ' ';
        g <<'\n';
    }
}