Cod sursa(job #3372582)

Utilizator ananicoletaRosca Ana-Nicoleta ananicoleta Data 4 noiembrie 2026 12:34:05
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

const int MAXN = 100005;
int n,m,timer;
vector<vector<int>> adj(MAXN);
vector<int> low(MAXN);
vector<int> dfn(MAXN);
vector<vector<int>> componente;
vector<bool> in_stack(MAXN, false);
stack<int> stiva;

void dfs(int current) {
    dfn[current]=low[current]=++timer;
    stiva.push(current);
    in_stack[current]=true;

    for (int vecin : adj[current]) {
        if (!dfn[vecin]) {
            dfs(vecin);
            low[current]=min(low[current],low[vecin]);
        }else if (in_stack[vecin]){
            low[current]=min(low[current],dfn[vecin]);
        }
    }
    if (low[current]==dfn[current]) {
        vector<int> comp;
        while (true) {
            int node=stiva.top();
            stiva.pop();
            in_stack[node]= false;
            comp.push_back(node);
            if (node==current) break;
        }
        componente.push_back(comp);
    }
}

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

    for (int i=1;i<=n;i++) {
        if (!dfn[i]) dfs(i);
    }

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