Cod sursa(job #3344136)

Utilizator Roberto_CChirvasitu Roberto Roberto_C Data 1 martie 2026 14:05:31
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long

const int NMAX = 1e5;
int n,m,k;
vector<int>v[NMAX+1];
vector<int>rev[NMAX+1];
bitset<NMAX+1>vap;
vector<int>topo;
vector<int>tare[NMAX+1];

void dfs(int nod){
    vap[nod] = 1;
    for(int i : v[nod]){
        if(!vap[i])
            dfs(i);
    }
    topo.push_back(nod);
}

void dfs2(int nod,int k){
    vap[nod] = 1;
    tare[k].push_back(nod);
    for(int i : rev[nod]){
        if(!vap[i])
            dfs2(i,k);
    }
}

void read(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int st,dr;
        cin >> st >> dr;
        v[st].push_back(dr);
        rev[dr].push_back(st);
    }
}

void solve(){
    for(int i = 1; i <= n; i++){
        if(!vap[i]){
            dfs(i);

        }
    }
    vap.reset();
    reverse(topo.begin(),topo.end());
    /*for(int i : topo)
        cout << i << ' ';*/
    for(int i : topo){
        if(!vap[i]){
            dfs2(i,k);
            k++;
        }
    }
    cout << k << '\n';
    for(int i = 0; i < k; i++){
        for(int j : tare[i])
            cout << j << ' ';
        cout << '\n';
    }
}

int main() {
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    read();
    solve();
    return 0;
}