Cod sursa(job #3371282)

Utilizator StefanVVulpoiu Stefan StefanV Data 29 octombrie 2026 16:47:22
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>

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

vector <int> h[100003];
vector <int> g[100003];
vector <int> scc[100003];

int n, m, nrc;
int st[100003], viz[100003], top;

void DFS(int n)
{
    viz[n] = 1;
    for (int i : h[n])
        if (viz[i] == 0)
            DFS(i);
    st[++top] = n;
}

void DFS2(int n)
{
    viz[n] = 0;
    for (int i : g[n])
        if (viz[i] == 1)
            DFS2(i);
    scc[nrc].push_back(n);
}

void SCC()
{
    for (int i=1; i<=n;i++)
        if (viz[i]==0)
            DFS(i);
    for (int i=n; i>0; i--)
        if (viz[st[i]] == 1)
        {
            nrc++;
            DFS2(st[i]);
        }
}

void Afis()
{
    fout << nrc << "\n";
    for (int i=1; i<=nrc; i++)
    {
        for (int j : scc[i])
            fout << j << " ";
        fout << "\n";
    }
}
int main()
{
    fin >>n>>m;
    for (int i=1; i<=m; i++)
    {
        int x, y;
        fin >>x>>y;
        h[x].push_back(y);
        g[y].push_back(x);
    }
    SCC();
    Afis();
    return 0;
}