Cod sursa(job #3269647)

Utilizator stefan0211Tacu Darius Stefan stefan0211 Data 20 ianuarie 2025 10:39:11
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <set>
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m;
vector<set<int>> la, la_t;
queue<vector<int>> componenta_tare_conexa;
stack<int> stiva_kosajaru;
vector<bool> viz;

void Read()
{
    f >> n >> m;

    la.resize(n + 1);
    la_t.resize(n + 1);
    viz.resize(n + 1, false);

    for (int i = 1; i <= m; i++)
    {
        int u, v;
        f >> u >> v;
        la[u].insert(v);
        la_t[v].insert(u);
    }
}

void DFS(vector<set<int>> &la, int nod_start)
{
    viz[nod_start] = true;

    for (auto &v : la[nod_start])
    {
        if (viz[v])
            continue;
        else
            DFS(la, v);
    }

    // când nodul este finalizat
    stiva_kosajaru.push(nod_start);
}
void DFS_kosajaru(vector<set<int>> &la, int nod_start)
{
    componenta_tare_conexa.back().push_back(nod_start);
    viz[nod_start] = true;

    for (auto &v : la[nod_start])
    {
        if (viz[v])
            continue;
        else
            DFS_kosajaru(la, v);
    }
}

int main()
{
    Read();

    for (int i = 1; i <= n; i++)
    {
        if (viz[i] == false)
            DFS(la, i);
    }

    viz.assign(n + 1, false);
    while (!stiva_kosajaru.empty())
    {
        int nod = stiva_kosajaru.top();
        stiva_kosajaru.pop();
        if (viz[nod] == false)
        {
            componenta_tare_conexa.emplace();
            DFS_kosajaru(la_t, nod);
        }
    }

    g << componenta_tare_conexa.size() << '\n';
    while (!componenta_tare_conexa.empty())
    {
        for (auto &v : componenta_tare_conexa.front())
        {
            g << v << " ";
        }
        g << '\n';
        componenta_tare_conexa.pop();
    }

    return 0;
}