Cod sursa(job #2510297)

Utilizator nicolaefilatNicolae Filat nicolaefilat Data 16 decembrie 2019 11:38:02
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <iostream>
#include <fstream>
#include <vector>

const int MAXN = 100000 + 5;

using namespace std;

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

vector<int>graf[MAXN];
vector<int>stiva_curenta;
bool stiva[MAXN];
int index_global,viz[MAXN];
vector<vector<int> >componente;
int up[MAXN],n,m;

void bagareComp(int nod){
    int i;
    vector<int>curent;
    for(i = stiva_curenta.size() - 1; stiva_curenta[i] != nod; i--){
        curent.push_back(stiva_curenta[i]);
        stiva[stiva_curenta[i]] = false;
        stiva_curenta.pop_back();
    }

    curent.push_back(stiva_curenta[i]);
    stiva[stiva_curenta[i]] = false;
    stiva_curenta.pop_back();


    componente.push_back(curent);


}

void dfs(int nod){
    stiva[nod] = true;
    viz[nod] = ++index_global;
    up[nod] = viz[nod];
    stiva_curenta.push_back(nod);

    int curent;
    for(int i = 0; i < graf[nod].size(); i++){
        int curent = graf[nod][i];
        if(viz[curent] > 0){
            if(stiva[curent]){
                up[nod] = min(up[nod],viz[curent]);
            }
        }else{
            dfs(curent);
            up[nod] = min(up[nod], up[curent]);
        }
    }

    if(up[nod] == viz[nod])bagareComp(nod);
}


int main()
{
    in>>n>>m;
    for(int i = 1; i <= m; i++){
        int x,y;
        in>>x>>y;
        graf[x].push_back(y);
    }
    for(int i = 1; i <= n; i++){
        if(!viz[i]){
            dfs(i);
        }
    }
    out<<componente.size()<<"\n";
    for(int i = 0; i < componente.size(); i++){
        for(auto j : componente[i])
            out<<j<<" ";
        out<<"\n";
    }
    return 0;
}