Cod sursa(job #3296212)

Utilizator Andrei-Dani-10Pisla Andrei Daniel Andrei-Dani-10 Data 12 mai 2025 10:11:57
Problema Componente tare conexe Scor 0
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <fstream>
#include <queue>
#include <vector>

///#pragma GCC optimize("O3", "unroll-loops")

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];

vint chain[nmax + 2];

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

/**void bfs(int node){
    queue <int> dq;
    dq.push(node);
    clan[node] = node;

    for(int noww; !dq.empty(); ){
        noww = dq.front();
        out<<noww<<" "; dq.pop();
        for(auto nxt : nextt[noww]){
            if(!clan[nxt]){
                clan[nxt] = node;
                dq.push(nxt);
            }
        }
    }
    out<<"\n";

    return;
}**/

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[flagg].push_back(node);
    for(auto nxt : reversegraph[node])
        if(clan[nxt]) dfsinv(nxt);
    ///postordine[++countt] = node;

    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]){
            flagg = i;
            dfsnorm(i);
        }
    }

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

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

    return 0;
}