Cod sursa(job #2926077)

Utilizator SteanfaDiaconu Stefan Steanfa Data 16 octombrie 2022 21:15:07
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#include <iostream>
#include <fstream>
// #include "Graph.cc"
#include <vector>
#include <deque>
#include <algorithm>
const int nrMagic = 100001;

int low[nrMagic], id[nrMagic], revId[nrMagic];
std::vector<std::vector<int>> v(nrMagic);
std::vector<int> viz(nrMagic, 0);
std::deque<int> stack;
int ret = 0, inc = 1, tine = 0;
std::vector<std::vector<int>> parc(nrMagic);
void dfs(const int &nod)
{
    // Facem o parcurgere dfs normala doar ca fiecarui nod ii asociem un id si un lowlink value 
    viz[nod] = 1;
    stack.push_back(inc); //punem intr-o stiva id-urile nodurilor 
    low[nod] = inc; // valoarea minima a nodurilor in care putem merge
    revId[inc] = nod; // id -> actual nod
    id[nod] = inc++; //actual nod -> id
    for (auto &&i : v[nod])
    {
        if (viz[i] == 0)
        {
            dfs(i);
        }
        // cand terminam parcurgerea facem update la low daca nodul nu face parte deja dintr-o componenta conexa 
        if (std::find(stack.begin(), stack.end(), id[i]) != stack.end())
        {
            low[nod] = std::min(low[nod], low[i]);
        }
    }
    if (id[nod] == low[nod]) // daca am gasit o componenta conexa
    {

        while (stack.back() != id[nod])
        {
            parc[tine].push_back(revId[stack.back()]);
            stack.pop_back();
        }
        parc[tine].push_back(revId[stack.back()]);
        stack.pop_back();

        ret++;
        tine++;
    }

}
// Complexitate: O(m + n)

int main()
{
    std::ifstream cin("ctc.in");
    std::ofstream cout("ctc.out");
    unsigned int n, m;
    cin >> n >> m;

    for (size_t i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
    }


    for (size_t i = 1; i <= n; i++)
    {
        if (viz[i] == 0)
        {
            dfs(i);
        }
    }
    cout << ret << '\n';
    for (size_t i = 0; i < tine; i++)
    {
        for (auto &&j : parc[i])
        {
            cout << j << " ";
        }

        cout << "\n";
    }
}