Cod sursa(job #3331968)

Utilizator gabi072Sanda Gabriel gabi072 Data 2 ianuarie 2026 12:34:26
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define pb push_back
vector<int> v[100001],ct[100001];
int onst[100001],id[100001],low[100001],idcurent,cate;
stack<int> s;
void tarjan(int n){
    onst[n]=1;
    id[n]=low[n]=++idcurent;
    s.push(n);
    for(int i:v[n]){
        if(!id[i])
            tarjan(i);
        if(onst[i])
            low[n]=min(low[n],low[i]);
    }
    if(low[n]==id[n]){
        int top;
        cate++;
        do{
            top=s.top();
            ct[cate].pb(top);
            low[top]=id[n];
            onst[top]=0;
            s.pop();

        }while(top!=n);
    }
}
int main(){
    int n,m;
    fin>>n>>m;
    for(int i=1;i<=m;++i){
        int x,y;
        fin>>x>>y;
        v[x].pb(y);
    }
    for(int i=1;i<=n;++i){
        if(!id[i])
            tarjan(i);
    }
    fout<<cate<<'\n';
    for(int i=1;i<=cate;++i){
        for(int j:ct[i])
            fout<<j<<" ";
        fout<<'\n';
    }
}