Cod sursa(job #3296220)

Utilizator Andrei-Dani-10Pisla Andrei Daniel Andrei-Dani-10 Data 12 mai 2025 10:19:58
Problema Componente tare conexe Scor 100
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <vector>

using namespace std;

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

typedef vector <int> vint;
const int nmax = 100000;
int n, m, a, b, clan[nmax + 2];
vint nextt[nmax + 2], chain[nmax + 2];

vint reversegraph[nmax + 2];
int postordine[nmax + 2], countt, tareconex;

int flagg;
void dfsnorm(int node){
    clan[node] = 1;

    for(auto nxt : nextt[node])
        if(!clan[nxt]) dfsnorm(nxt);

    postordine[++countt] = node;
    return;
}

void dfsinv(int node){

    clan[node] = 0; ///out<<node<<" ";
    chain[tareconex].push_back(node);

    for(auto nxt : reversegraph[node])
        if(clan[nxt]) dfsinv(nxt);

    return;
}

int main(){

    in>>n>>m;
    for(int i = 1; i <= m; i++){
        in>>a>>b;
        nextt[a].push_back(b);
        reversegraph[b].push_back(a);
    }

    countt = 0;
    for(int i = 1; i <= n; i++){
        if(!clan[i]){
            dfsnorm(i);
        }
    }

    ///countt = 0;
    for(int i = n; i >= 1; i--){
        if(clan[postordine[i]]){
            tareconex++;
            dfsinv(postordine[i]);
        }
    }

    out<<tareconex<<"\n";
    for(int i = 1; i <= tareconex; i++){
        for(auto it : chain[i])
            out<<it<<" ";
        out<<"\n";
    }

    return 0;
}