Cod sursa(job #3371096)

Utilizator AnlegliftIvanus Victor Gabriel Anleglift Data 28 octombrie 2026 17:33:42
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int MAXN = 100005;
vector<int> graph[MAXN];
vector<vector<int>> componente;

int global_index;

bool on_stack[MAXN];
int node_index[MAXN];
int low[MAXN];

stack<int> node_stack;

void DFS(int node)
{
    node_index[node] = low[node] = ++global_index;
    on_stack[node] = true;
    node_stack.push(node);

    for (int neighbour : graph[node])
    {
        if (node_index[neighbour] == 0)
        {
            DFS(neighbour);
            low[node] = min(low[node], low[neighbour]);
        }
        else if (on_stack[neighbour])
        {
            low[node] = min(low[node], node_index[neighbour]);
        }
    }

    if (low[node] == node_index[node])
    {
        vector<int> componenta;

        while (true)
        {
            int current_node = node_stack.top();
            node_stack.pop();

            on_stack[current_node] = false;
            componenta.push_back(current_node);

            if (current_node == node)
                break;
        }
        componente.push_back(componenta);
    }
}

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

    for (int i = 0; i < m; ++i)
    {
        int a, b;
        fin >> a >> b;
        graph[a].push_back(b);
    }

    DFS(1);

    fout << componente.size() << "\n";
    for (const auto &componenta : componente)
    {
        for (int node : componenta)
        {
            fout << node << " ";
        }
        fout << endl;
    }
    return 0;
}