Cod sursa(job #3269035)

Utilizator ioanabaduIoana Badu ioanabadu Data 18 ianuarie 2025 10:28:31
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

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

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

    for (auto idx:graph[x]){
        if (id[idx] == 0){ // nu am mai fost pe acolo
            dfs(idx);
            low[x] = min(low[x], low[idx]);
        }   
        else if (inStack[idx] == true){ // ii un back edge care perge in sus 
            low[x] = min(low[x], id[idx]);
        }
    }

    if (low[x] == id[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] == 0){
            dfs(i);
        }
    }

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

    return 0;
}