Cod sursa(job #3294830)

Utilizator dragospatakiDragospataki dragospataki Data 29 aprilie 2025 09:37:06
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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


stack <int> s;
int low_link[100002];
int id[100002];
int viz[100002];
int on_stack[100002];
int cct=1;
int n,m;
int idem;
vector <int> adj[100002];
vector <int> rez[100002];
void  dfs(int nod){
    id[nod]=++idem; 
    low_link[nod]=idem;   
    s.push(nod);
    on_stack[nod]=1;
    viz[nod]=1;
    for(auto neighboar : adj[nod]){
        if(viz[neighboar]==0){
            dfs(neighboar);
        }
        if(on_stack[neighboar]==1){
            low_link[nod]=min(low_link[nod],low_link[neighboar]);
        }
    }
    if(id[nod]==low_link[nod]){
        while(true){
            int top=s.top();
            on_stack[s.top()]=0;
            rez[cct].push_back(s.top());
            s.pop();
            if(top==nod)
            break;
        }
        cct++;
    }
}
int main(){
    in>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b;
        in>>a>>b;
        adj[a].push_back(b);
        //adj[b].push_back(a);
    }
    for(int i=1;i<=n;i++){
        if(viz[i]==0){  
            dfs(i);
        }
    }

    out<<cct-1<<'\n';
    for(int i=1;i<cct;i++){
        for( auto it : rez[i]){
            out<<it<<" ";
        }
        out<<'\n';
    }
    return 0;
}