Cod sursa(job #3322171)

Utilizator Alex283810Mocan Alexandru Vali Alex283810 Data 12 noiembrie 2025 23:04:45
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>

std::vector<std::vector<int>>a;

int timer = 0;
int disc[50001], low[50001];
bool apc[50001];
int nr_con = 0;

std::vector<int>con;
std::vector<std::vector<int>>ans;

void tarzan(int from)
{
    disc[from] = low[from] = ++timer;
    con.push_back(from);
    apc[from] = 1;
    for(auto to : a[from])
    {
        if(!disc[to])
        {
            tarzan(to);
            low[from] = std::min(low[from], low[to]);
        }
        else if(apc[to])
        {
            low[from] = std::min(low[from], disc[to]);
        }
    }
    if(low[from] == disc[from])
    {
        std::vector<int> component;
        while(true) {
            int node = con.back();
            con.pop_back();
            apc[node] = false;
            component.push_back(node);
            if(node == from) break;
        }
        ans.push_back(component);
        nr_con++;
    }
}
int main()
{
    freopen("output.txt", "w", stdout);

    int n, m;
    std::cin >> n >> m;

    a.resize(n + 1, std::vector<int>());

    for(int i = 0; i < m; i++)
    {
        int x, y;
        std::cin >> x >> y;
        a[x].push_back(y);
    }
    for(int i = 1; i <= n; i++)
    {
        if(disc[i] == 0)
            tarzan(i);
    }
    std::cout << nr_con << '\n';
    for(auto &v : ans)
    {
        for(int b : v)
            std::cout << b << ' ';
        std::cout << '\n';
    }
}