Cod sursa(job #2784804)

Utilizator realmeabefirhuja petru realmeabefir Data 17 octombrie 2021 13:47:04
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
// TARJAN IMPLEMENTATION
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

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

vector<int> la[100000];
stack<int> st;
int onStack[100000];
int ids[100000];
int lowLink[100000];
int id = 0;
int ctc = 0;
vector<vector<int>> ctcV;

int n,m;

void dfs(int nod)
{
    st.push(nod);
    onStack[nod] = 1;
    ids[nod] = id;
    lowLink[nod] = id;
    id ++;

    for (auto& el: la[nod])
    {
        if (ids[el] == -1)
            dfs(el);
        if (onStack[el])
        {
            lowLink[nod] = min(lowLink[nod], lowLink[el]);
        }
    }

    if (ids[nod] == lowLink[nod])
    {
        ctcV.push_back(vector<int>());
        int nod_curent = st.top();
        st.pop();
        ctcV[ctc].push_back(nod_curent);
        while (nod_curent != nod)
        {
            onStack[nod_curent] = 0;
            nod_curent = st.top();
            st.pop();
            ctcV[ctc].push_back(nod_curent);
        }
        ctc++;
    }

}

int main()
{
    in >> n >> m;
    for (int i = 0; i < n; i++)
        ids[i] = -1;

    for (int i = 0; i < m; ++i)
    {
        int n1, n2;
        in >> n1 >> n2;
        la[n1-1].push_back(n2-1);
    }

    for (int i = 0; i < n; i++)
    {
        if (ids[i] == -1)
            dfs(i);
    }

    out << ctc << '\n';
    for (auto& rand: ctcV)
    {
        for (auto& el: rand)
            out << el+1 << ' ';
        out << '\n';
    }

    return 0;
}