Cod sursa(job #3336052)

Utilizator and_Turcu Andrei and_ Data 24 ianuarie 2026 04:16:33
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>



using namespace std;



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

int n, m, th_time;
const int N = 100007;
vector<int> a[N], disc(N, 0), l_link(N, 0), still_open(N, 0);
map<int, vector<int>> comp;
int ct_comp;
stack<int> nodes;

void DFS(int x)
{
    l_link[x] = disc[x] = ++th_time;
    still_open[x] = 1;
    nodes.push(x);

    for(auto y: a[x])
    {
        if(!disc[y])
            DFS(y);

        if(still_open[y])
           l_link[x] = min(l_link[x], l_link[y]);
    }

    if(l_link[x] == disc[x])
    {
        ct_comp++;

        while(nodes.top() != x)
        {
            comp[ct_comp].push_back(nodes.top());
            nodes.pop();
        }
        comp[ct_comp].push_back(nodes.top());
        nodes.pop();
    }
}



int main()
{
    fin >> n >> m;

    for(int i = 1; i <= m; i++)
    {   
        int x, y;
        fin >> x >> y;
        a[x].push_back(y);
    }

    for(int i = 1; i <= n; i++)
        if(!disc[i])
            DFS(i);

    fout << comp.size() << "\n";

    for(auto w: comp)
    {
        for(auto x: w.second)
            fout << x << " ";
        fout << "\n";
    }

    return 0;
}