Cod sursa(job #2206795)

Utilizator b2xdBilaniuc Dragos b2xd Data 23 mai 2018 20:26:24
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <vector>
#define DIM 100001

std::ifstream f("ctc.in");
std::ofstream g("ctc.out");

struct Node{
    bool taken;
};

std::vector<int> G[DIM],sol[DIM],q;
Node node[DIM];
int n,m,k=0;

void read(){
    f>>n>>m;
    int x,y;
    for(int i=1;i<=m;i++){
        f>>x>>y;
        G[x].push_back(y);
    }
    f.close();
}

void init(){
    for(int i=1;i<=n;i++){
        node[i].taken= false;
    }
}

void DFS_visit_p(int x){
    node[x].taken=true;
    for(int y:G[x]){
        if(!node[y].taken){
            DFS_visit_p(y);
            q.push_back(y);
        }
    }
}

void DFS_p(){
    init();
    for(int i=1;i<=n;i++){
        if(!node[i].taken) {
            DFS_visit_p(i);
            q.push_back(i);
        }
    }
}

void invert(){
    std::vector<int> G1[DIM];
    for(int i=1;i<=n;i++)
        for(int j:G[i])
            G1[j].push_back(i);
    for(int i=1;i<=n;i++)
        G[i]=G1[i];
}

void DFS_visit(int x){
    node[x].taken=true;
    sol[k].push_back(x);
    for(int y:G[x]){
        if(!node[y].taken){
            DFS_visit(y);
        }
    }
}

void DFS(){
    init();
    while (!q.empty()){
        int x=q.back();
        q.pop_back();
        if(!node[x].taken) {
            DFS_visit(x);
            k++;
        }
    }
}

void kosaraju(){
    DFS_p();
    invert();
    DFS();
}

void print(){
    g<<k<<"\n";
    for(int i=0;i<k;i++){
        for(int j:sol[i]){
            g<<j<<" ";
        }
        g<<"\n";
    }
    g.close();
}


int main() {
    read();
    kosaraju();
    print();
    return 0;
}