Cod sursa(job #3374518)

Utilizator lea_Lea Ales lea_ Data 9 noiembrie 2026 01:40:29
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> adj[100005];
int vizitat[100005], low[100005];
bool onStack[100005];
int cnt=0;
vector<vector<int>> comps;
vector<int> stack;

void dfs(int v){
    vizitat[v]=low[v]=++cnt;
    stack.push_back(v);
    onStack[v]=true;

    for(int u:adj[v]){
        if(!vizitat[u]){
            dfs(u);
            low[v]=min(low[v],low[u]);
        } else if(onStack[u]){
            low[v]=min(low[v],vizitat[u]);
        }
    }

    if(low[v]==vizitat[v]){
        vector<int> c;
        int w;
        do{
            w=stack.back();
            stack.pop_back();
            onStack[w]=false;
            c.push_back(w);
        } while(w!=v);
        comps.push_back(c);
    }
}


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

    int n,m;
    fin>>n>>m;

    for(int i=0; i<m; i++){
        int x,y;
        fin>>x>>y;
        adj[x].push_back(y);
    }

    for(int i=1; i<=n; i++)
        if(!vizitat[i])
            dfs(i);
    
    fout<<comps.size()<<"\n";

    for(auto c:comps) {
        for(int x:c) 
            fout<<x<<" ";
        fout<<"\n";
    }
    return 0;
}