Cod sursa(job #2328173)

Utilizator andaraluca2001Anda Epure andaraluca2001 Data 25 ianuarie 2019 14:53:45
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

const int MAX= 100003;

vector <int> gr[MAX], comp[MAX];

stack <int> s, afis;

bool viz[MAX];

int n, m, id[MAX], low[MAX], nc, urm;

ifstream in("ctc.in");

ofstream out("ctc.out");

void tarjan(int nod){

    id[nod] = low[nod] = ++urm;

    s.push(nod);

    viz[nod] = true;

    for(unsigned i=0; i<gr[nod].size(); i++)

        if(id[gr[nod][i]]==0){

            tarjan(gr[nod][i]);

            low[nod] = min(low[nod], low[gr[nod][i]]);

        }

        else

            if(viz[gr[nod][i]]==true)

                low[nod] = min(low[nod], low[gr[nod][i]]);

    if(id[nod] == low[nod]){

        nc++;

        int v;

        do{

            v = s.top();

            s.pop(); viz[v] = false;

            afis.push(v);

        }while(v!=nod);

    }



}

int main()

{

    int i, u, v;

    in>>n>>m;

    for(i=1; i<=m; i++){

    in>>u>>v;

        gr[u].push_back(v);

    }

    for(i=1; i<=n; i++)

        if(id[i]==0)

            tarjan(i);

    out<<nc;

    while(!afis.empty()){

        int v = afis.top();

        afis.pop();

        if(id[v] == low[v]) out<<'\n';

        out<<v<<' ';

    }

    return 0;

}