Cod sursa(job #2928872)

Utilizator federicisFedericis Alexandru federicis Data 24 octombrie 2022 00:46:53
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <iterator>
#include <algorithm>

using namespace std;

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

vector <int> graf[100000], con, idx, lowlink, in_stack;

vector < vector <int> > componente;

stack <int> S;

int index;

void print_out(const vector < vector <int> >& G)
{


}

void tarjan(int nod)
{
    idx[nod] = index;
    lowlink[nod] = index;
    index ++;
    S.push(nod), in_stack[nod] = 1;

    for (auto& vecin : graf[nod]) {
        if (idx[vecin] == -1){
            tarjan(vecin);
            lowlink[nod] = min(lowlink[nod], lowlink[vecin]);
        }
        else if (in_stack[vecin])
            lowlink[nod] = min(lowlink[nod], lowlink[vecin]);
    }
    if (idx[nod] == lowlink[nod]) {
        con.clear();
        int node;
        do {
            con.push_back(node = S.top());
            S.pop(), in_stack[node] = 0;
        }
        while (node != nod);
        componente.push_back(con);
    }
}

int main()
{
    int n, m, x, y;
    in >> n >> m;
    for (int i = 1; i <= m; i++){
        in >> x >> y,
        graf[x].push_back(y);
    }
    idx.resize(n + 1), lowlink.resize(n + 1), in_stack.resize(n + 1);
    idx.assign(n + 1, -1), in_stack.assign(n + 1, 0);
    for (int i = 1; i <= n; ++ i)
        if (idx[i] == -1)
            tarjan(i);

    out << componente.size() << "\n";
    for (int i = 0; i < componente.size(); ++ i) {
        for (int j = 0; j < componente[i].size(); ++ j)
            out << componente[i][j] << " ";
        out << "\n";
    }

    return 0;
}