Cod sursa(job #2338822)

Utilizator RK_05Ivancu Andreea Raluca RK_05 Data 7 februarie 2019 20:55:23
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#define nmax 100005

using namespace std;

ifstream fin("date.in");
//ifstream fin("ctc.in");
//ofstream fout("ctc.out");

vector <int> G1[nmax], G2[nmax], sol[nmax];
int n, m, x, y, viz[nmax], nr_el;
stack <int> S;

void read(){
    fin >> n >> m;
    for(int i = 1; i <= m; ++i){
        fin >> x >> y;
        G1[x].push_back(y);
        G2[y].push_back(x);
    }
}

void DFS1(int nod){
    viz[nod] = 1;
    for(int i = 0; i < G1[nod].size(); ++i)
        if(!viz[G1[nod][i]])
            DFS1(G1[nod][i]);
    S.push(nod);
}

void DFS2(int nod){
    viz[nod] = 2;
    sol[nr_el].push_back(nod);
    for(int i = 0; i < G2[nod].size(); ++i)
        if(viz[G2[nod][i]] == 1)
            DFS2(G2[nod][i]);
}

void kosaraju(){
    for(int i = 1; i <= n; ++i)
        if(viz[i] == 0)
            DFS1(i);
    while(!S.empty()){
        if(viz[S.top()] == 1){
            nr_el++;
            DFS2(S.top());
        }
        S.pop();
    }
    cout << nr_el << endl;
    for(int i = 1; i <= nr_el; ++i){
        for(int j = 0; j < sol[i].size(); ++j)
            cout << sol[i][j] << " ";
        cout << endl;
    }
}

int main(){
    read();
    kosaraju();
    fin.close();
//    fout.close();
    return 0;
}