Cod sursa(job #2426256)

Utilizator Dragos123Tatar Dragos Vlad Dragos123 Data 27 mai 2019 09:11:58
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

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

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

int n, m;
int index;

VI sc, idx, lowLink;
VB inStack;

VVI G, sol;
std::stack<int> stk;

void Read();
void Tarjan(int i);
void Solve();
void Write();

int main()
{
    Read();
    Solve();
    Write();

    fin.close();
    fout.close();

    return 0;
}

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

    G = VVI(n + 1);

    int x, y;

    for (int i = 0; i < m; ++i)
    {
        fin >> x >> y;

        G[x - 1].push_back(y - 1);
    }
}

void Tarjan(int i)
{
    idx[i] = lowLink[i] = index;
    index++;
    stk.push(i);
    inStack[i] = true;

    for (const auto& x : G[i])
    {
        if (idx[x] == -1)
        {
            Tarjan(x);
            lowLink[i] = std::min(lowLink[i], lowLink[x]);
        }

        else if (inStack[x])
            lowLink[i] = std::min(lowLink[i], lowLink[x]);
    }

    if (idx[i] == lowLink[i])
    {
        sc.clear();
        int node = 0;

        do
        {
            node = stk.top();
            sc.push_back(node);
            stk.pop();
            inStack[node] = false;
        } while(i != node);

        sol.push_back(sc);
    }
}

void Solve()
{
    idx = VI(n + 1, -1);
    lowLink = VI(n + 1);
    inStack = VB(n + 1);

    for (int i = 0; i < n; ++i)
        if (idx[i] == -1)
            Tarjan(i);
}

void Write()
{
    fout << sol.size() << '\n';

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