Cod sursa(job #3343795)

Utilizator tudorhTudor Horobeanu tudorh Data 28 februarie 2026 15:29:22
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

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

const int nmax = 1e5;
vector<int>v[nmax + 1], vr[nmax + 1], comp[nmax + 1];
int componente;
stack<int>s;
bool vap[nmax + 1];
void dfs (int nod) {
    vap[nod] = 1;
    for (int i : v[nod])
        if (!vap[i])
            dfs (i);
    s.push (nod);
}
void dfsr (int nod) {
    comp[componente].pb (nod);
    vap[nod]=1;
    for (int i : vr[nod])
        if (!vap[i])
            dfsr (i);
}

int main() {
    ios_base::sync_with_stdio (false);
    cin.tie (nullptr);
    int n, m;
    fin >> n >> m;
    while (m--) {
        int st, dr;
        fin >> st >> dr;
        v[st].pb (dr);
        vr[dr].pb (st);
    }
    for (int i = 1; i <= n; i++)
        if (!vap[i])
            dfs (i);
    fill(vap+1,vap+n+1,0);
    while (!s.empty() ) {
        int t=s.top();
        s.pop();
        if(vap[t])
            continue;
        componente++;
        dfsr(t);
    }
    fout<<componente<<'\n';
    for(int i=1;i<=componente;i++){
        for(int j:comp[i])
            fout<<j<<' ';
        fout<<'\n';
    }
    return 0;
}