Cod sursa(job #3344177)

Utilizator IleaIlea Bogdan Ilea Data 1 martie 2026 16:03:25
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include<iostream>
#include<vector>
#include<stack>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;

#define NMAX 100001

int n,m;
vector<int>g[NMAX],rg[NMAX];
vector<vector<int>>cc;
bitset<NMAX>b;
stack<int>s;
void dfs(int i){
    b[i]=true;
    for(auto it:g[i]){
        if(b[it])continue;
        dfs(it);
    }
    s.push(i);
}
void rdfs(int i){
    b[i]=true;
    cc.back().push_back(i);
    for(auto it:rg[i]){
        if(b[it])continue;
        rdfs(it);
    }
}
signed main(){
#ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#endif // LOCAL
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        rg[y].push_back(x);
    }
    for(int i=1;i<=n;++i){
        if(b[i])continue;
        dfs(i);
    }
    b.reset();
    while(!s.empty()){
        int i=s.top();
        s.pop();
        if(b[i])continue;
        cc.push_back({});
        rdfs(i);
    }
    cout<<cc.size()<<"\n";
    for(auto it=cc.begin();it!=cc.end();++it){
        sort(it->begin(),it->end());
        for(auto val=it->begin();val!=it->end();++val){
            cout<<*val<<" ";
        }
        cout<<"\n";
    }
    return 0;
}