Cod sursa(job #3341844)

Utilizator ioanabaduIoana Badu ioanabadu Data 21 februarie 2026 12:50:31
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 100005

using namespace std;

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

vector <int> graph[NMAX], ctc[NMAX];
vector <int> stack;
bool inStack[NMAX];
int id[NMAX], low[NMAX];
int nodes, edges, numCtc, num;

void tarjan (int x){
    id[x] = ++num;
    low[x] = id[x];
    inStack[x] = true;
    stack.push_back(x);

    for (auto neighbour:graph[x]){
        if (!id[neighbour]){ // never been here before
            tarjan(neighbour);
            low[x] = min(low[x], low[neighbour]);
        }
        else if (inStack[neighbour]) // backedge
            low[x] = min(low[x], id[neighbour]);
    }

    if (id[x] == low[x]){
        while (stack.back() != x){
            ctc[numCtc].push_back(stack.back());
            inStack[stack.back()] = false;
            stack.pop_back();
        }

        ctc[numCtc].push_back(stack.back());
        inStack[stack.back()] = false;
        stack.pop_back();

        numCtc++;
    }
}

int main (){
    int x, y;

    in >> nodes >> edges;
    for (int i=1; i<=edges; ++i){
        in >> x >> y;
        graph[x].push_back(y);
    }

    for (int i=1; i<=nodes; ++i){
        if (!id[i]) tarjan(i);
    }

    out << numCtc << '\n';
    for (int i=0; i<numCtc; ++i){
        for (auto idx:ctc[i])
            out << idx << ' ';
        out << '\n';
    }

    return 0;
}