Cod sursa(job #3347968)

Utilizator moloDaniMolodet Andrei Daniel moloDani Data 19 martie 2026 09:40:04
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int mxN = 1e5 + 1;

vector<int> G[mxN], Gt[mxN];
stack<int> ordine;

int n, m, componenta[mxN];
bool parcurs[mxN];

void DFS(int nod){
    parcurs[nod] = true;
    for(auto x : G[nod]){
        if(!parcurs[x])
            DFS(x);
    }
    ordine.push(nod);
}

void conex(int nod, int culoare){
    componenta[nod] = culoare;
    for(auto x : Gt[nod]){
        if(!componenta[x])
            conex(x, culoare);
    }
}

int main(){
    int cul = 0;
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        int a, b;
        fin >> a >> b;
        G[a].push_back(b);
        Gt[b].push_back(a);
    }

    for(int i = 1; i <= n; i++){
        if(!parcurs[i])
            DFS(i);
    }

    while(!ordine.empty()){
        if(!componenta[ordine.top()])
            conex(ordine.top(), ++cul);

        ordine.pop();
    }

    fout << cul << "\n";
    vector<vector<int>> comp(cul + 1);
    for(int i = 1; i <= n; i++)
        comp[componenta[i]].push_back(i);
    for(int c = 1; c <= cul; c++){
        for(auto x : comp[c])
            fout << x << " ";
        fout << "\n";
    }
}