Cod sursa(job #2169813)

Utilizator RaduVFVintila Radu-Florian RaduVF Data 14 martie 2018 17:51:54
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

ifstream fin ( "ctc.in" );
ofstream fout ( "ctc.out" );
const int mmax = 200005, nmax = 100005;
int N, M, x, y, ssc, comp;
bool viz1[nmax];
int viz2[nmax];
vector < int > G[mmax],GT[mmax],sol[nmax];
stack < int > stiva;

void Citire () {
    fin >> N >> M;
    for(int i = 1; i <= M; i++) {
        fin >> x >> y;
        G[x].push_back(y);
        GT[y].push_back(x); // graf transpus
    }
}

void DFS1 (int nod) {
    viz1[nod] = true;
    for(unsigned i = 0; i < G[nod].size(); i++) {
        int v = G[nod][i];
        if (!viz1[v]) DFS1(v);
    }
    stiva.push(nod);
}

void DFS2 (int nod) {
    viz2[nod] = comp;
    sol[comp].push_back(nod);
    for(unsigned i = 0; i < GT[nod].size(); i++) {
        int v = GT[nod][i];
        if (!viz2[v]) DFS2(v);
    }
}
int main()
{
    Citire();
    DFS1(1);
    for (int i = 2; i <= N; i++)
        if(!viz1[i]) DFS1(i);
    while(!stiva.empty()) {
        ssc=stiva.top();
        stiva.pop();
        if(viz2[ssc]==0){
            comp++;
            DFS2(ssc);
        }
    }
    fout << comp << "\n";
    for (int i = 1; i <= comp; i++) {
        for(unsigned j = 0; j<sol[i].size(); j++)
            fout << sol[i][j] << ' ';
        fout << endl;
    }
    return 0;
}