Cod sursa(job #2159293)

Utilizator SenibelanMales Sebastian Senibelan Data 10 martie 2018 20:59:15
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int NMAX = 100005;
int N, M;
int Component;
vector <int> G[NMAX];
vector <int> R[NMAX];
vector < vector<int> > sol;
stack <int> t;
bool UseTopo[NMAX], Use[NMAX];

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

void DFSTopo(int node){
    UseTopo[node] = true;
    for(int i = 0; i < G[node].size(); ++i){
        int neighbour = G[node][i];
        if(!UseTopo[neighbour])
            DFSTopo(neighbour);
    }
    t.push(node);
}

void DFSComponent(int node){
    Use[node] = true;
    sol[sol.size() - 1].push_back(node);
    for(int i = 0; i < R[node].size(); ++i){
        int neighbour = R[node][i];
        if(!Use[neighbour])
            DFSComponent(neighbour);
    }
}

void Solve(){
    for(int i = 1; i <= N; ++i)
        if(!UseTopo[i])
            DFSTopo(i);
    while(!t.empty()){
        int node = t.top();
        t.pop();
        if(!Use[node]){
            vector <int> v;
            sol.push_back(v);
            DFSComponent(node);
        }
    }
}

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

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