Cod sursa(job #1766693)

Utilizator meriniucrMeriniuc Razvan- Dumitru meriniucr Data 28 septembrie 2016 13:36:59
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 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] > l[v[node][i]])
            {
                l[node] = l[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;
}