Cod sursa(job #1766638)

Utilizator meriniucrMeriniuc Razvan- Dumitru meriniucr Data 28 septembrie 2016 11:19:01
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <fstream>
#include <stack>
#include <vector>

std::ifstream mama("ctc.in");
std::ofstream tata("ctc.out");

std::vector <int> v[100001];
std::vector <std::vector <int> > components;
std::stack <int> s;

int vindex[100001];
int l[100001];
bool onStack[100001];
int n;
int m;
int counterIndex;

    void
go(int node)
{
    int vertex;
    int size;

    vindex[node] = counterIndex;
    l[node] = counterIndex;
    ++counterIndex;
    s.push(node);
    onStack[node] = true;

    for (int i = 0; i < (int)v[node].size(); ++i)
    {
        if (not vindex[v[node][i]])
        {
            go(v[node][i]);
            if (l[node] > l[v[node][i]])
            {
                l[node] = l[v[node][i]];
            }
        }
        else if (onStack[v[node][i]])
        {
            if (l[node] > vindex[v[node][i]])
            {
                l[node] = vindex[v[node][i]];
            }
        }
    }

    if (l[node] == vindex[node])
    {
        components.push_back(std::vector <int> ());
        size = (int)components.size() - 1;
        do
        {
            vertex = s.top();
            s.pop();
            onStack[vertex] = false;
            components[size].push_back(vertex);
        } while (vertex != node);
    }
}

int main()
{
    mama >> n;
    mama >> m;

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

    counterIndex = 1;
    for (int i = 1; i <= n; ++i)
    {
        if (not vindex[i])
        {
            go(i);
        }
    }

    tata << components.size() << '\n';

    for (const auto& comp : components)
    {
        for (const auto& it : comp)
        {
            tata << it << ' ';
        }

        tata << '\n';
    }
    
    return 0;
}