Cod sursa(job #2087097)

Utilizator SenibelanMales Sebastian Senibelan Data 12 decembrie 2017 21:46:48
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <vector>

using namespace std;

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


const int NMAX = 100005;
vector <int> G[NMAX];
vector <int> Ginv[NMAX];
vector <int> sol[NMAX];
int N, M;
int conexe;
int comp[NMAX];
int pred[NMAX], succ[NMAX];

void Read(){
    in >> N >> M;
    for(int i = 1; i <= M; ++i){
        int a, b;
        in >> a >> b;
        G[a].push_back(b);
        Ginv[b].push_back(a);
    }
}

void Forw(int node){
    succ[node] = conexe;
    for(int i = 0; i < G[node].size(); ++i){
        int neighbour = G[node][i];
        if(!succ[neighbour])
            Forw(neighbour);
    }
}

void Backw(int node){
    pred[node] = conexe;
    for(int i = 0; i < Ginv[node].size(); ++i){
        int neighbour = Ginv[node][i];
        if(!pred[neighbour])
            Backw(neighbour);
    }
}

void Merge(){
    for(int i = 1; i <= N; ++i){
        if(pred[i] == succ[i] && pred[i] == conexe)
            sol[conexe].push_back(i); 
        else if(pred[i] != succ[i])
            pred[i] = succ[i] = 0;
    }
}

void Solve(){
    for(int i = 1; i <= N; ++i){
        if(!succ[i]){
            conexe++;
            Forw(i);
            Backw(i);
            Merge();
        }
    }
}

void Print(){
    out << conexe << "\n";
    for(int i = 1; i <= conexe; ++i){
        for(int j = 0; j < sol[i].size(); ++j)
            out << sol[i][j] << " ";
        out << "\n";
    }
}

int main(){
    Read();
    Solve();
    Print();
}