Cod sursa(job #2789469)

Utilizator cezar.balutaCezar Baluta cezar.baluta Data 27 octombrie 2021 16:12:30
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;

ifstream in("ctc.in");
ofstream out("ctc.out");
int cnt=0;
vector<int>succesori[100500];
vector<int>predecesori[100500];
int sortare_topologica[100500];
vector<int>raspuns[100000];
bitset<100500>viz;
int lungime=1;

void dfs2(int x){
    viz[x]=0;
    for(auto y:predecesori[x]){
        if(viz[y]==1){
            cout<<y;
            dfs2(y);
        }
    }
    raspuns[cnt].push_back(x);
}

void dfs (int x){
    viz[x]=1;
    for(auto y:succesori[x]){
        if(viz[y]==0){
            dfs(y);
        }
    }
    sortare_topologica[lungime++]=x;
}

int main() {
    int n,m,x,y;
    in>>n>>m;
    for(int i=0;i<m;i++){
        in>>x>>y;
        succesori[x].push_back(y);
        predecesori[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        if(viz[i]==0)
        dfs(i);
    }
    for(int i=n;i>0;i--){
        if(viz[sortare_topologica[i]]){
            dfs2(sortare_topologica[i]);
            cnt++;
        }
    }
    out<<cnt<<"\n";
    for(int i=0;i<cnt;i++) {
        for (auto x: raspuns[i])
            out << x << " ";
        out<<"\n";
    }

    return 0;


}