Cod sursa(job #3374311)

Utilizator xeneyzeAl Daraghmeh Omar-Sorin xeneyze Data 8 noiembrie 2026 22:37:10
Problema Componente tare conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<vector<int>> g, gt;
vector<bool> viz;
vector<int> ordine;
vector<vector<int>> comp;

void dfs1(int nod) {
    viz[nod]=true;
    for ( int v : g[nod])
        if ( !viz[v]) dfs1(v);
    ordine.push_back(nod);
}

void dfs2(int nod) {
    viz[nod]=true;
    for ( int v : gt[nod])
        if ( !viz[v]) dfs2(v);
}

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

    fin>>n>>m;
    g.resize(n+1);
    gt.resize(n+1);
    for ( int i=0; i<m; i++) {
        int a, b;
        fin>>a>>b;
        g[a].push_back(b);
        gt[b].push_back(a);
    }

    viz.assign(n+1, false);
    for ( int i=1; i<=n; i++)
        if ( !viz[i]) dfs1(i);

    viz.assign(n+1, false);
    for ( int i=n-1; i>=0; i--) {
        int nod=ordine[i];
        if ( !viz[nod]) {
            comp.push_back({nod});
            dfs2(nod);
        }
    }

    fout<<comp.size()<<"\n";
    for ( auto &c : comp) {
        for ( int x : c) fout<<x<<" ";
        fout<<"\n";
    }
    return 0;
}