Cod sursa(job #1550809)

Utilizator HashiraGrigore Vlad Hashira Data 14 decembrie 2015 18:56:53
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <fstream>

#include <vector>
#include <stack>

int n;

std::vector < std::vector < int > > adj_list, components;
std::vector < int > comp, low, in_stack, c;

std::stack < int > st;

int comps;

void tarjan(int u)
{
    comp[u] = low[u] = comps++;
    st.push(u);
    in_stack[u] = 1;

    std::size_t i;
    for(i = 0 ; i < adj_list[u].size() ; ++i)
    {
        int v = adj_list[u][i];

        if(comp[v] == -1)
        {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        }
        else if(in_stack[v])
        {
            low[u] = std::min(low[u], low[v]);
        }
    }

    if(comp[u] == low[u])
    {
        c.clear();

        int node;
        while(node != u)
        {
            node = st.top();
            st.pop();
            c.push_back(node);
            in_stack[node] = 0;
        }

        components.push_back(c);
    }
}

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

    fin >> n;

    adj_list.assign(n + 1, std::vector < int >());
    comp.assign(n + 1, -1);
    low.assign(n + 1, 0);
    in_stack.assign(n + 1, 0);

    int m;
    fin >> m;

    int node_a, node_b;
    for(int i = 1 ; i <= m ; ++i)
    {
        fin >> node_a >> node_b;
        adj_list[node_a].push_back(node_b);
    }

    for(int i = 1 ; i <= n ; ++i)
        if(comp[i] == -1)
            tarjan(i);

    fout << components.size() << "\n";
    for(std::size_t i = 0 ; i < components.size() ; ++i)
    {
        for(std::size_t j = 0 ; j < components[i].size() ; ++j)
            fout << components[i][j] << " ";

        fout << "\n";
    }

    return 0;
}