Cod sursa(job #3372928)

Utilizator bexxRebeca N bexx Data 5 noiembrie 2026 16:43:39
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <bitset>
#include <vector>
#include <stack>
using namespace std;

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

int n,m,cnt=0;
const int N=1e5+3;
stack<int>S;
bitset<N>viz;
vector<vector<int>>g;
vector<vector<int>>t;
vector<vector<int>>ctc;

void graph() {
    cin>>n>>m;
    g.resize(n+1);
    t.resize(n+1);
    int x,y;
    for (int i=0;i<m;i++) {
        cin>>x>>y;
        g[x].push_back(y);
        t[y].push_back(x);
    }
}
void dfs1(int nod) {
    viz[nod]=1;
    for (auto v: g[nod])
        if (!viz[v])
            dfs1(v);
    S.push(nod);
}

void dfs2(int nod) {
    viz[nod]=1;
    ctc[cnt].push_back(nod);
    for (auto v : t[nod])
        if (!viz[v])
            dfs2(v);
}

int main() {
    graph();
    viz.reset();
    for (int i=1;i<=n;i++)
        if (!viz[i])
            dfs1(i);
    viz.reset();
    while (!S.empty()) {
        int i= S.top();
        S.pop();
        if (!viz[i]) {
            ctc.push_back({});
            dfs2(i);
            cnt++;
        }
    }
    cout<<ctc.size()<<'\n';
    for (int i=0;i<ctc.size();i++,cout<<'\n')
        for (auto x: ctc[i])
            cout<<x<<' ';
    return 0;
}