Cod sursa(job #2960522)

Utilizator alin_simpluAlin Pop alin_simplu Data 4 ianuarie 2023 16:10:07
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.12 kb
// 13 PM

#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

using VI  = vector<int>;
using VB  = vector<bool>; 
using VVI = vector<VI>;

VVI G;  // the graph
VI c;   // current component
VVI ctc; // stores all components
VB P;   // P[x] = true if the node x is visited
VB InStack;            // InStack[x] = true if the node x is currently in Stack
VI indexx, low_index;   // stores the index and the low index of all nodes
stack<int> stk;

int n, m;
int idx;

void ReadGraph();
void Tarjan();
void DF(int x);
void Extract_comp(int x);
void Print_comp();

int main(){
    ReadGraph();
    Tarjan();
    Print_comp();
    
    return 0;
}

void Print_comp(){
    fout << ctc.size() << '\n';

    for (auto const& C : ctc)
    {
        for (auto const& node : C)
            fout << node << ' ';
        fout << '\n';
    }
}

void DF(int x){
    P[x] = true;
    indexx[x] = low_index[x] = ++idx;
    stk.emplace(x);
    InStack[x] = true;

    for (int const& y : G[x])
        if (!P[y]){   // daca y este fiul lui x
            DF(y);
            low_index[x] = min(low_index[x], low_index[y]);
        }
        else
            if (InStack[y])  // daca y este stramos al lui x (x -> y == back edge)
               low_index[x] = min(low_index[x], indexx[y]);

    if (indexx[x] == low_index[x]) // if x is the representant of a new component
        Extract_comp(x);
}

void Extract_comp(int x){
    c.clear();    // clear the vector for a new component

    while (!stk.empty()){
        int node = stk.top();
        stk.pop();
        InStack[node] = false;

        c.push_back(node);

        if (node == x)   // if all the nodes of the component have been stored 
           break; 
    }

    ctc.emplace_back(c);
}

void Tarjan(){
    for (int node = 1; node <= n; ++node)
        if (!P[node])
            DF(node);
}

void ReadGraph(){
    fin >> n >> m;

    G = VVI(n + 1);     // initializations
    low_index = VI(n + 1);
    indexx = VI(n + 1);
    P = InStack = VB(n + 1);
   
    int x, y;
    while (m--){
        fin >> x >> y;
        G[x].emplace_back(y);
    }
}